Merge Sort

Merge sort algorithm based on divide, conquer and combine algorithmic paradigm. In this, we break the element lists into pieces, process the pieces and at last put them all together.

This is the simplest sorting algorithm. It takes efficient space time complexity.

These are the processes that mergesort follows -

• Divide - It partitions the n elements of array into two sub arrays.
• Conquer - It sorts the two sub arrays using merge sort.
• Combine - It merges the two sorted sequences to produce the sorted array.

Merge Sort Example

These are the merge sorting technique. We have the following lists of array element.

Here, we have taken pairs of array elements and sort them.

Now combine the two pairs and sort them.

Merge the sorted subsequences and again, sort them.

Complexity of Merge Sort

Suppose n is the number of elements in an array.

Best Time Complexity - O(n)
Worst Time Complexity - O(n2)
Average Time Complexity - O(n2)

Merge Sort Program in C

#include<stdio.h>
#include<conio.h>

#define MAX 20

void mergesort(int, int);
void merge_data(int, int, int, int);

int arrsort[MAX];

int main() {
  int i, count;

  printf("Enter the number of elements: \n");
  scanf("%d", &count);
  printf("\nEnter %d numbers\n", count);
  for (i = 0; i < count; i++)
    scanf("%d", &arrsort[i]);

  printf("\nElement List  :");
  for (i = 0; i < count; i++) {
    printf("\t%d", arrsort[i]);
  }

  mergesort(0, count - 1);

  printf("\n\nSorted List :");
  for (i = 0; i < count; i++) {
    printf("\t%d", arrsort[i]);
  }
  getch();

}

void mergesort(int i, int j) {
  int m;

  if (i < j) {
    m = (i + j) / 2;
    mergesort(i, m);
    mergesort(m + 1, j);
    // Merge both arrays
    merge_data(i, m, m + 1, j);
  }
}

void merge_data(int a, int b, int c, int d) {
  int t[50];
  int i = a, j = c, k = 0;

  while (i <= b && j <= d) {
    if (arrsort[i] < arrsort[j])
      t[k++] = arrsort[i++];
    else
      t[k++] = arrsort[j++];
  }

  while (i <= b)
    t[k++] = arrsort[i++];

  while (j <= d)
    t[k++] = arrsort[j++];

  for (i = a, j = 0; i <= d; i++, j++)
    arrsort[i] = t[j];
}

Output of the above program:

Enter the number of elements: 
10

Enter 10 numbers
21
31
42
12
14
53
63
23
32
64

Element List  :	21	31	42	12	14	53	63	23	32	64

Sorted List :	12	14	21	23	31	32	42	53	63	64