MergeSort Algorithm

ALGORITHM Mergesort(A[0..n - 1])

//Sorts array A[0..n - 1] by recursive mergesort
//Input: An array A[0..n - 1] of orderable elements
//Output: Array A[0..n - 1] sorted in nondecreasing order

if n > 1
copy A[0..n/2 - 1] to B[0..n/2 - 1]
copy A[n/2..n - 1] to C[0..n/2 - 1]

Mergesort(B[0..n/2 - 1])Mergesort(C[0..n/2 - 1])

Merge(B, C, A) 


ALGORITHM Merge(B[0..p - 1],C[0..q - 1],A[0..p + q - 1])

//Merges two sorted arrays into one sorted array
//Input: Arrays B[0..p - 1] and C[0..q - 1] both sorted
//Output: Sorted array A[0..p + q - 1] of the elements of B and C

i ← 0; 

j ← 0; 

k ← 0

while i < p and j < q do

if B[i] ≤ C[j]

A[k] ← B[i]; i ← i + 1

else

A[k] ← C[j]; j ← j + 1

k ← k + 1

if i = p

copy C[j..q - 1] to A[k..p + q - 1]

else

copy B[i..p - 1] to A[k..p + q - 1]


C program:

#include<stdio.h>
void mergesort (int[], int);
void merge (int[], int[], int[], int, int, int);
main ()
{
  int n, a[20], b[20], c[20], i;
  printf ("enter size of array\n");
  scanf ("%d", &n);
  printf ("enter the elements\n");
  for (i = 0; i < n; i++)
{    scanf ("%d", &a[i]);}
  mergesort (a, n);
  printf ("SORTED ARRAY\n");
  for (i = 0; i < n; i++)
   { printf ("%d\t", a[i]);}
}

void mergesort (int a[10], int n)
{
  int b[10], c[10], i, j = 0, k;
  if (n > 1)
    {
      for (i = 0; i < n / 2; i++, j++)
        b[j] = a[i];
         k=0;
      for (; i < n; i++, k++)

          c[k] = a[i];
          mergesort (b, j);
          mergesort (c, k);
          merge (b, c, a, j, k, n);
    }
}
  void merge( int b[], int c[], int a[], int j, int k, int n)
  {
    int p = 0, q = 0, r = 0, l;
    while (p < j && q < k)
      {
        if (b[p] <= c[q])
          {
            a[r] = b[p];
            p++;
          }
 else
          {
            a[r] = c[q];
            q++;
          }
        r++;
      }
    if (p == j)
      {
        for (l = q; l <= k - 1; l++, r++)
          {
            a[r] = c[l];
          }
      }
    else
     {
        for (l = p; l <= j - 1; r++, l++){
          a[r] = b[l];
      }
  }
}

Output:

enter size of array
5
enter the elements
2
3
1
5
6
SORTED ARRAY
1       2       3       5       6