Home » Data Structure

Merge Sort with and without Recursion using C program

In this article, we are going to learn about merge sort and implementing c program with and without using recursion. By Manu Jemini, on January 24, 2018

Merge Sort with and Without Recursion

Merge Sort is base on divide and conquer algorithm.

1. DIVIDING

In Merge Sort, we take a middle index and break the array into two sub-arrays. These sub-array will go on breaking till the array have only one element.

2. MERGING

When all we have is single elements we start merging the elements in the same order in which we have divided them. During Merging, we also sort the sub-arrays, because sorting 10 arrays of 2 elements is cheaper than sorting an array of 20 elements.

In the end, we will have an array of elements, which is sorted.

C program to implement Merge Sort using Recursion

#include<stdio.h>

#define MAX 100

void merge(int array[], int low, int mid, int high) {
  int temp[MAX];
  int i = low;
  int j = mid + 1;
  int k = low;

  while ((i <= mid) && (j <= high)) {
    if (array[i] <= array[j])
      temp[k++] = array[i++];
    else
      temp[k++] = array[j++];
  } /*End of while*/

  while (i <= mid)
    temp[k++] = array[i++];

  while (j <= high)
    temp[k++] = array[j++];

  for (i = low; i <= high; i++)
    array[i] = temp[i];

} /*End of merge()*/

void merge_sort(int array[], int low, int high) {
  int mid;
  if (low != high) {
    mid = (low + high) / 2;
    merge_sort(array, low, mid);
    merge_sort(array, mid + 1, high);
    merge(array, low, mid, high);
  }
} /*End of merge_sort*/

int main() {
  int i, n;
  int array[MAX];

  printf("Enter the number of elements : ");
  scanf("%d", & n);
  for (i = 0; i < n; i++) {
    printf("Enter element %d : ", i + 1);
    scanf("%d", & array[i]);
  }

  printf("Unsorted list is :\n");
  for (i = 0; i < n; i++)
    printf("%d ", array[i]);

  merge_sort(array, 0, n - 1);

  printf("\nSorted list is :\n");
  for (i = 0; i < n; i++)
    printf("%d ", array[i]);
  printf("\n");

  return 0;
} /*End of main()*/

Output