Jyotiprakash's Blog

Merge Sort

Jyotiprakash Mishra's photo
Jyotiprakash Mishra
·

8 min read

Merge sort is a popular sorting algorithm that uses the divide-and-conquer approach. It divides the input array into two halves, sorts each half, and then merges the two sorted halves. Here's a step-by-step explanation of how merge sort works, using an example array with 10 elements. We'll also include ASCII art to illustrate each iteration.

Suppose we have an array: [38, 27, 43, 3, 9, 82, 10, 33, 19, 15]

Step 1: Divide the Array

Initially, the entire array is divided into two halves.

  • First Half: [38, 27, 43, 3, 9]

  • Second Half: [82, 10, 33, 19, 15]

Step 2: Recursively Sort Each Half

Each half is further divided until we have subarrays with only one element, which are inherently sorted.

                            [38, 27, 43, 3, 9, 82, 10, 33, 19, 15]
                                  /                           \
                [38, 27, 43, 3, 9]                             [82, 10, 33, 19, 15]
                  /            \                                 /               \
          [38, 27]            [43, 3, 9]                 [82, 10]             [33, 19, 15]
          /    \               /      \                  /     \               /       \
       [38]  [27]          [43]     [3, 9]             [82]   [10]           [33]    [19, 15]
                                /       \                                          /      \
                             [3]        [9]                                     [19]     [15]

Step 3: Merge Each Subarray

Now, the subarrays are merged in a sorted manner. This step is where the "conquer" part of divide-and-conquer comes into play.

[27, 38] [3, 9, 43]   [10, 82]     [15, 19, 33]
   \        /             \             /
 [3, 9, 27, 38, 43]    [10, 15, 19, 33, 82]
            \                         /
             [3, 9, 10, 15, 19, 27, 33, 38, 43, 82]

After this division, the merge steps begin, combining and sorting smaller arrays into larger, sorted arrays, until the entire array is sorted. This process results in a final sorted array: [3, 9, 10, 15, 19, 27, 33, 38, 43, 82].

The beauty of merge sort is in its efficiency, especially for large arrays. It has a time complexity of O(n log n), which makes it very efficient for sorting large datasets.

Here's a pseudocode for the Merge Sort algorithm along with explanations for each part. Merge Sort is a recursive divide-and-conquer algorithm that sorts an array by dividing it into halves, sorting each half, and then merging the sorted halves.

Pseudocode

Function MergeSort(Array A, int start, int end)
    if start < end
        int middle = (start + end) / 2
        MergeSort(A, start, middle)     // Sort the first half
        MergeSort(A, middle + 1, end)   // Sort the second half
        Merge(A, start, middle, end)    // Merge the sorted halves

Function Merge(Array A, int start, int middle, int end)
    Create array L[0..middle-start+1]  // Left subarray
    Create array R[0..end-middle]      // Right subarray

    // Copy data to temporary subarrays L[] and R[]
    for i = 0 to middle-start
        L[i] = A[start + i]
    for j = 0 to end-middle-1
        R[j] = A[middle + 1 + j]

    // Merge the temp arrays back into A[start..end]
    int i = 0, j = 0, k = start
    while i < length(L) and j < length(R)
        if L[i] <= R[j]
            A[k] = L[i]
            i++
        else
            A[k] = R[j]
            j++
        k++

    // Copy the remaining elements of L[], if any
    while i < length(L)
        A[k] = L[i]
        i++
        k++

    // Copy the remaining elements of R[], if any
    while j < length(R)
        A[k] = R[j]
        j++
        k++

Explanation

  1. MergeSort Function:

    • This is the main function that implements Merge Sort.

    • It recursively divides the array into halves until each subarray contains a single element.

    • MergeSort(A, start, middle) sorts the first half of the array.

    • MergeSort(A, middle + 1, end) sorts the second half of the array.

    • Merge(A, start, middle, end) merges the two sorted halves.

  2. Merge Function:

    • This function merges two sorted subarrays into a single sorted array.

    • It creates two temporary arrays, L and R, to hold the left and right halves of the array, respectively.

    • The elements of the main array (A) are then copied into these temporary arrays.

    • The function then compares the elements of L and R and copies the smaller element back into the main array A.

    • If there are remaining elements in either L or R after this process, these elements are copied back into A to ensure that all elements are merged.

  3. Divide and Conquer Approach:

    • Merge Sort uses a divide-and-conquer approach.

    • The array is divided into smaller subarrays (divide), each of which is sorted (conquer), and then the sorted subarrays are merged (combine).

  4. Time Complexity:

    • The time complexity of Merge Sort is O(n log n) in all cases (worst, average, and best), which makes it very efficient for sorting large datasets.

Merge Sort is particularly useful for large datasets and performs well on linked lists and arrays. It's also stable, meaning it preserves the order of equal elements, which can be important in certain applications.

Here's a C implementation of the Merge Sort algorithm along with a detailed explanation of each part:

C Code for Merge Sort

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temp arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

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

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

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Find the middle point
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

// Utility function to print an array
void printArray(int A[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

// Test the code
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

Explanation

  1. Function merge:

    • This function merges two subarrays of arr[].

    • arr[l..m] and arr[m+1..r] are the two subarrays that need to be merged.

    • Two temporary arrays L[] and R[] are created to hold the values of the subarrays.

    • The contents of arr[] are copied into L[] and R[].

    • The two arrays are then merged back into arr[], sorting them in the process.

  2. Function mergeSort:

    • This is a recursive function that divides the array into two halves, calls itself for the two halves, and then merges the two sorted halves.

    • The division of the array is done by calculating the middle index m.

    • Recursive calls are made for the ranges l to m and m+1 to r.

  3. Utility Function printArray:

    • This function prints the contents of an array. It is used to show the array before and after sorting.

  4. The main Function:

    • It initializes an array arr and determines its size.

    • The array is printed, sorted using mergeSort, and then printed again to show the sorted array.

Usage and Performance

  • Merge Sort is particularly useful for sorting large datasets because of its O(n log n) time complexity for all cases (worst, average, and best).

  • It's a stable sort, meaning it preserves the order of equal elements, which is an important property in some sorting applications.

  • However, Merge Sort requires O(n) additional space for the temporary arrays, which can be a drawback for very large arrays.

Complexity analysis of Merge Sort involves evaluating both its time complexity and space complexity.

Time Complexity

  1. Divide Step:

    • This step simply divides the array into two halves and takes constant time, O(1).

  2. Recursive Calls:

    • Merge Sort repeatedly divides the array in half until each sub-array has one element. The division can be represented as a tree, where each level represents a recursive call that divides the array. Since the array is divided in half each time, the height of the tree (or the number of levels) is log(n), where n is the number of elements in the array.

  3. Merge Step:

    • At each level of the tree, the algorithm iterates over all n elements to merge them. This operation has a time complexity of O(n).

  4. Overall Time Complexity:

    • Since there are log(n) levels (height of the tree) and each level requires O(n) time for merging, the overall time complexity of Merge Sort is O(n log n).

Space Complexity

  1. Auxiliary Space for Merging:

    • Merge Sort requires additional space for the temporary arrays used during the merge process. For each merge, an additional space proportional to the size of the sub-arrays being merged is required. This space requirement is O(n) where n is the number of elements in the array.

  2. Recursion Stack Space:

    • The recursive implementation of Merge Sort also uses stack space. The depth of the recursion tree is log(n), so the space used in the call stack is O(log n).

  3. Overall Space Complexity:

    • Combining the space for the temporary arrays and the recursion call stack, the overall space complexity of Merge Sort is O(n + log n), which simplifies to O(n) as the O(log n) term is dominated by O(n).

Important to note

  • Time Complexity: O(n log n) for all cases (best, average, worst).

  • Space Complexity: O(n) due to the auxiliary space needed for temporary arrays.

This analysis reveals that Merge Sort is very efficient in terms of time, especially for large datasets. However, its space inefficiency (requiring O(n) extra space) can be a drawback in memory-constrained environments.

merge sortsorting algorithmsalgorithms