Merge Sort

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input list into smaller sub-lists, recursively sorts them, and then merges the sorted sub-lists to produce a final sorted list.

Algorithm

1. Divide the unsorted list into n sub-lists, each containing one element.
2. Repeatedly merge sub-lists to produce new sorted sub-lists until there is only one sub-list remaining.

PseudoCode

   Merge-Sort(A, P, R)
1. if (P > R)
2.     Q <--- ⌊ ( P + R ) / 2 ⌋
3.     Merge-Sort(A, P, Q)
4.     Merge-Sort(A, Q + 1, R)
5.     Merge(A, P, Q, R)
6. Stop

   Merge(A, P, Q, R)
1. n1 <--- Q - P + 1
2. n2 <--- R - Q
3. Create Array LEFT[1 ... n1 + 1] and RIGHT[1 ... n2 + 1]
4. for i <--- 1 to n1
5.     LEFT[ i ] <--- A[ P + i + 1 ]
6. for j <--- 1 to n2
7.     RIGHT[ j ] <--- A[ Q + j]
8. LEFT[ n1 + 1 ] <--- ∞
9. RIGHT[ n2 + 1 ] <--- ∞
10. i <--- 1
11. j <--- 1
12. for k <--- P to R
13.     if( LEFT[ i ] <= R[ j ])
14.         A[ k ] <--- LEFT[ i ]
15.         i <--- i + 1
16.     else
17.         A[ k ] <--- RIGHT[ i ]
18.         j <--- j + 1

Implementation in C Programming Language

#include <stdio.h>
#include <limits.h>

int array[10];

void input_array(int[], int);
void print_array(int[], int);
void merge_sort(int[], int, int);
void merge(int[], int, int, int);

void main()
{
    input_array(array, 5);
    merge_sort(array, 1, 5);
    print_array(array, 5);
}

void input_array(int A[], int N)
{
    int i;

    printf("Enter the values for sorting :-\n");
    for (i = 1; i <= N; i++)
    {
        printf("Value %d :", i);
        scanf("%d", &A[i]);
    }
}

void print_array(int A[], int N)
{
    int i;

    printf("\nSorted array is : {");
    for (i = 1; i <= N; i++)
    {
        printf("%d, ", A[i]);
    }
    printf("}");
}

void merge_sort(int A[], int P, int R)
{
    int Q;

    if (P < R)
    {
        Q = (P + R) / 2;
        merge_sort(A, P, Q);
        merge_sort(A, Q + 1, R);
        print_array(array, 5);
        merge(A, P, Q, R);
    }
}

void merge(int A[], int P, int Q, int R)
{
    int n1, n2, i, j, k;

    n1 = Q - P + 1;
    n2 = R - Q;

    int LEFT[n1 + 1], RIGHT[n2 + 1];

    for (i = 1; i <= n1; i++)
        LEFT[i] = A[P + i - 1];

    for (j = 1; j <= n1; j++)
        RIGHT[j] = A[Q + j];

    LEFT[n1 + 1] = INT_MAX;
    RIGHT[n2 + 1] = INT_MAX;

    i = 1, j = 1;

    for (k = P; k <= R; k++)
    {
        if (LEFT[i] <= RIGHT[j])
        {
            A[k] = LEFT[i];
            i++;
        }
        else
        {
            A[k] = RIGHT[j];
            j++;
        }
    }
}

Working

1. Divide:

   • Split the unsorted list into two halves.
   • Recursively divide each sub-list until each sub-list contains only one element.

2. Conquer:

   • Merge the sub-lists in a bottom-up manner.
   • Compare elements from the two sub-lists and merge them in sorted order.

3. Combine:

   • Continue merging sub-lists until a single sorted list is obtained.

Visualization

    [5, 3]          [8, 4, 2]         --> Pass 1 (Divide)
      / \              / \
   [5]  [3]       [8]   [4, 2]        --> Pass 2 (Divide)
      / \              / \  
   [3]  [5]        [4, 2] [8]         --> Pass 3 (Conquer)
              / \
      [2, 4, 8]  [3, 5]               --> Pass 4 (Combine)
              \ /
       [2, 3, 4, 5, 8]                --> Final Sorted List

Consider an example:

Original List: 5, 3, 8, 4, 2

Pass 1 (Divide):

• Split into [5, 3] and [8, 4, 2]

Pass 2 (Divide):

• Split into [5] and [3]
• Split into [8] and [4, 2]

Pass 3 (Conquer):

• Merge [5] and [3] to get [3, 5]
• Merge [8] and [4, 2] to get [4, 2, 8]

Pass 4 (Combine):

• Merge [3, 5] and [4, 2, 8] to get [2, 3, 4, 5, 8]

Time Complexity

• Worst, average, and best case: O(n log n)

Space Complexity

• O(n) - Merge Sort requires additional space proportional to the size of the input list.

Stability

• Merge Sort is stable, meaning the relative order of equal elements remains unchanged after sorting.