Merge Sort Algorithm

Merge Sort Algorithm

Merge Sort is a Divide and Conquer sorting algorithm that divides an array into two halves, recursively sorts each half, and then merges the two sorted halves. This algorithm is efficient and works well for large datasets. It has a time complexity of O(n log n) in all cases (best, worst, and average), which makes it one of the more efficient sorting algorithms for large datasets.

Steps in Merge Sort

The Merge Sort algorithm follows three main steps:

1. Divide: Split the input array into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves back into a single sorted array.

Merge Sort Algorithm: Detailed Explanation

1. Divide

The first step in Merge Sort is to divide the unsorted array into two halves. If the array contains only one element, it is already sorted (since a single element is trivially sorted).

2. Conquer (Recursively Sort)

The algorithm then recursively sorts the two halves by applying the same strategy: divide the halves further until each subarray has only one element.

3. Combine (Merge)

Once we have the smallest subarrays (containing one element each), the merge step begins. The merge step takes two sorted subarrays and combines them into a single sorted array.

During the merge process, we compare the smallest (leftmost) elements of the two subarrays, insert the smaller element into the result array, and move the pointer for that subarray. This process continues until all elements from both subarrays are merged into the final sorted array.

Merge Sort Pseudocode

Here is the pseudocode for the Merge Sort algorithm:

// Merge function to merge two sorted halves
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // Length of the left subarray
    int n2 = right - mid;     // Length of the right subarray
    
    // Temporary arrays to store the two halves
    int leftArr[n1], rightArr[n2];
    
    // Copy data to temporary arrays leftArr[] and rightArr[]
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
        rightArr[i] = arr[mid + 1 + i];
    }
    
    // Merge the temporary arrays back into arr[left...right]
    int i = 0;  // Initial index of leftArr[]
    int j = 0;  // Initial index of rightArr[]
    int k = left;  // Initial index of merged subarray
    
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    
    // Copy the remaining elements of leftArr[], if any
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    
    // Copy the remaining elements of rightArr[], if any
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// MergeSort function to recursively divide and sort the array
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // Find the middle point
        
        // Recursively sort the first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

Example Walkthrough of Merge Sort

Let’s walk through an example using the array:

[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide

• The array is split into two halves:
  • Left half: [38, 27, 43]
  • Right half: [3, 9, 82, 10]

Step 2: Recursively Sort the Left Half

• Split [38, 27, 43] into [38] and [27, 43].

  • [38] is already sorted (only one element).
  • Recursively sort [27, 43]:
    • Split [27, 43] into [27] and [43] (both are sorted).
    • Merge [27] and [43] into [27, 43].

• Now merge [38] and [27, 43]:

  • Compare 38 and 27. Since 27 is smaller, add 27 to the sorted array.
  • Compare 38 and 43. Since 38 is smaller, add 38 to the sorted array.
  • Add 43 to the sorted array.

• Sorted left half: [27, 38, 43].

Step 3: Recursively Sort the Right Half

• Split [3, 9, 82, 10] into [3, 9] and [82, 10].

  • Recursively sort [3, 9]:
    • Split [3, 9] into [3] and [9] (both are sorted).
    • Merge [3] and [9] into [3, 9].
  • Recursively sort [82, 10]:
    • Split [82, 10] into [82] and [10] (both are sorted).
    • Merge [82] and [10] into [10, 82].

• Now merge [3, 9] and [10, 82]:

  • Compare 3 and 10. Since 3 is smaller, add 3 to the sorted array.
  • Compare 9 and 10. Since 9 is smaller, add 9 to the sorted array.
  • Add 10 and 82 to the sorted array.

• Sorted right half: [3, 9, 10, 82].

Step 4: Combine the Sorted Halves

• Now merge the two sorted halves: [27, 38, 43] and [3, 9, 10, 82].

  • Compare 27 and 3. Since 3 is smaller, add 3 to the sorted array.
  • Compare 27 and 9. Since 9 is smaller, add 9 to the sorted array.
  • Compare 27 and 10. Since 10 is smaller, add 10 to the sorted array.
  • Compare 27 and 82. Since 27 is smaller, add 27 to the sorted array.
  • Compare 38 and 82. Since 38 is smaller, add 38 to the sorted array.
  • Compare 43 and 82. Since 43 is smaller, add 43 to the sorted array.
  • Add 82 to the sorted array.

• Final sorted array: [3, 9, 10, 27, 38, 43, 82].

Time Complexity of Merge Sort

• Best Case: O(n log n) — Merge Sort performs the same number of operations regardless of the initial order of elements, as it always divides and merges the array.
• Average Case: O(n log n) — Like the best case, the algorithm's time complexity remains the same for random input data.
• Worst Case: O(n log n) — The worst-case time complexity is also O(n log n), since the algorithm always divides the array in half and then merges the halves back together, regardless of input data.

Why O(n log n)?

• The array is divided into two halves at each recursive step, so there are O(log n) levels of recursion.
• At each level of recursion, all n elements need to be merged, which takes O(n) time.
• Thus, the total time complexity is O(n log n).

Space Complexity of Merge Sort

• Space Complexity: O(n)
  • Merge Sort requires additional space for storing the temporary subarrays during the merging step. This leads to a space complexity of O(n), where n is the number of elements in the array.

Advantages of Merge Sort

1. Stable: Merge Sort is a stable sorting algorithm, meaning that the relative order of equal elements is preserved.
2. Efficient for Large Datasets: Merge Sort’s time complexity is O(n log n) in all cases, making it efficient for large datasets.
3. Parallelizable: Merge Sort can be easily parallelized, making it suitable for multi-core processors.
4. Consistent Performance: Unlike other algorithms like Quick Sort, Merge Sort guarantees O(n log n) performance in the worst case.

Disadvantages of Merge Sort

1. Space Complexity: Merge Sort requires additional space (O(n