Merge Sort is a sorting algorithm based on the divide-and-conquer approach. It operates by recursively splitting the input array into smaller subarrays, sorting each subarray, and then merging them back together to produce the final sorted array.

In simpler terms, Merge Sort divides the array into two halves, sorts each half individually, and then combines the sorted halves. This process continues until the entire array is fully sorted.

Algorithm Steps

1. Divide: Split the input array into two halves recursively until each subarray contains only one element (base case).
2. Conquer: Sort the two halves recursively using Merge Sort.
3. Merge: Combine (merge) the two sorted halves into a single sorted array.

Pseudocode

Merge Sort(A, p,r)

1. p<r

2.         q=floor (p+r)/2

3.         Merge-Sort(A,p,q)

4.         Merge-Sort(A, q+1, r)

5.        Merge(A,p,q,r)

Merge (A,p,q,r)

1. n1=q-p+1

2. n2=r-q

3. let L[1…n1+1] and R[1….n2+1] be new array

4. for i-1 to n1

5.         L[i]=A[p+i-1]

6. for j=1 to n2

7.         R[j]=A[q-1]

8. L[n1+1]= infinite

9. R[n2+1]= infinite

10. i=1

11. j=1

12. for k=p to r

13.      if L[i]<=R[j]

14.          A[k]=L[i]

15.          i=i+1

16.     else A[k]=R[j]

17.             j=j+1

Time Complexity

• Best Case: O(nlogn)
• Average Case: (nlogn)
• Worst Case: O(nlogn)

Space Complexity

• O(n) due to the temporary arrays used for merging.

Advantages

1. Stable Sorting: Maintains the relative order of equal elements.
2. Guaranteed Performance: Always runs in O(nlog⁡n) time, regardless of input distribution.
3. Parallelizable: Its divide-and-conquer nature makes it suitable for parallel processing.

Disadvantages

1. Higher Memory Usage: Requires additional space for temporary arrays.
2. Less Cache-Friendly: Due to frequent creation of subarrays, it may not perform as efficiently on systems with limited cache.

Example

Final Sorted Array:

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

1. Divide the Array:

     Split the array into two halves:      Left: [38, 27, 43]

       Right: [3, 9, 82, 10]

2. Recursively Divide Each Half

     Left Half [38, 27, 43]:

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

     Right Half [3, 9, 82, 10]:

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

At this point, all subarrays have one element: [38], [27], [43], [3], [9], [82], [10]

3. Merge Step:

Merge the individual elements back together in sorted order.

• Merge [27] and [43]:

• Compare 27 and 43.
• Result: [27, 43]

Merge [38] and [27, 43]:

• Compare 38 with 27, then with 43.
• Result: [27, 38, 43]

Merge [3] and [9]:

• Compare 3 and 9

• Result: [3, 9]

Merge [82] and [10]:

• Compare 82 and 10.
• Result: [10, 82]

Merge [3, 9] and [10, 82]:

Compare 3 with 10, then 9 with 10, and finally 82.

• Result: [3, 9, 10, 82]

4. Final Merge:

Merge [27, 38, 43] and [3, 9, 10, 82]:

Compare each element:

• 3 < 27

• 9 < 27

• 10 < 27

• 27 < 38

• 38 < 43

• 43 < 82

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

Visualization of Each Step:

1. Split: [38, 27, 43, 3, 9, 82, 10]
2. Further splits:
3. Merging:
4. Final merge:

Program

#include"stdio.h"
#include"stdlib.h"

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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;
    j = 0;
    k = l;
    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++;
    }
}

// l is for left index and r is right index of the
// sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r - l) / 2;

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

        merge(arr, l, m, r);
    }
}

// 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");
}

// Driver 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;
}