Understanding Merge Sort by Using the Divide & Conquer Algorithm

Introduction

In this article, we will learn about the importance of the Divide and Conquer algorithm in solving data structure problems. The Divide and Conquer algorithm is a powerful problem-solving technique used in Programming. It works by breaking down a complex problem into smaller, more manageable subproblems, solving them independently, and then combining their solutions to solve the original problem. This approach can lead to efficient solutions for many computational problems.

Working of Divide and Conquer

The Divide and Conquer strategy follows three main steps.

• Divide: Break the problem into smaller subproblems.
• Conquer: Recursively solve the subproblems.
• Combine: Merge the solutions of the subproblems to create a solution to the original problem.

Let's take an Example of Merge Sort we will be solving the merge sort problem using the Divide and Conquer technique. Merge Sort is an efficient, stable sorting algorithm that uses the divide and conquer approach to sort an array of elements.

public class MergeSortExample {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int mid = (left + right) / 2;

            // Divide: Sort first and second halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Conquer: Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // Calculate sizes of two subarrays to be merged
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[mid + 1 + j];
        }

        // Merge the temporary arrays
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[] if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[] if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main method to test the MergeSort
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array:");
        printArray(arr);
    }

    // Utility method to print an array
    private static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Explanation of Merge Sort

• Divide: The mergeSort method recursively divides the array into two halves until we have subarrays of size 1.
• Conquer: Once we have subarrays of size 1, we start merging them back together. The merge method is responsible for this step.
• Combine: The merge method combines two sorted subarrays into a single sorted array. It compares elements from both subarrays and places them in the correct order in the original array.

The best thing about Merge Sort lies in its efficiency. It has a time complexity of O(n log n) for all cases, making it more efficient than simpler algorithms like Bubble Sort or Insertion Sort for large datasets.

Flow diagram of above merge sort example.

Advantages of Divide and Conquer

1. Efficiency: Many divide-and-conquer algorithms are efficient, often resulting in O(n log n) time complexity.
2. Parallelization: The independent subproblems can often be solved in parallel, potentially speeding up the solution on multi-core processors.
3. Solving complex problems: It allows us to break down complex problems into simpler, more manageable parts.

Summary

The Divide and Conquer algorithm is a fundamental technique in computer science, powering many efficient algorithms like Merge Sort, Quick Sort, and binary search. By breaking problems into smaller, manageable pieces, we can create elegant and efficient solutions to complex computational challenges.