C Program:Merge Sort

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. Idea: Divide the unsorted list into sublists, each containing element.

PROGRAM:

//merge_sort by Vikas Konaparthi
#include<stdio.h>
#include<conio.h>


void merge_sort(int, int,int arr_sort[50]);
void merge_array(int, int, int, int,int arr_sort[50]);
void ReadArray(int arr_sort[50],int);
void WriteArray(int arr_sort[50],int);


int main() {
  int i;
  int size = 5;
  int arr_sort[50];

  printf("Simple Merge Sort Example - Functions and Array\n");
  printf("\nEnter %d Elements for Sorting\n", size);
  ReadArray(arr_sort,size);

  printf("\nYour Data   :");
  for (i = 0; i < size; i++) {
    printf("\t%d", arr_sort[i]);
  }

  merge_sort(0, size - 1,arr_sort);

  WriteArray(arr_sort,size);
  getch();

}
void ReadArray(int arr_sort[50],int size)
{
    int i;
    for (i = 0; i < size; i++)
    scanf("%d", &arr_sort[i]);
}
void WriteArray(int arr_sort[50],int size)
{ int i;
    printf("\n\nSorted Data :");
  for (i = 0; i < size; i++) {
    printf("\t%d", arr_sort[i]);
  }
}

void merge_sort(int i, int j,int arr_sort[50]) {
  int m;

  if (i < j) {
    m = (i + j) / 2;
    merge_sort(i, m,arr_sort);
    merge_sort(m + 1, j,arr_sort);
    // Merging two arrays
    merge_array(i, m, m + 1, j,arr_sort);
  }
}

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

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

  //collect remaining elements
  while (i <= b)
    t[k++] = arr_sort[i++];

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

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