Simple Merge Sort Program in C

About this program

This is an example program in c sorting programs. Read the concept first: C Array, then study the code and output below.

Definition

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Conceptually, a merge sort works as: Divide the unsorted list into n sublists, each containing 1 element and repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Simple Merge Sort Program Example

/* Simple Merge Sort Program Using Functions and Array in C*/
/* Data Structure Programs,C Functions and Array Examples */

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

#define MAX_SIZE 5

void merge_sort(int, int);
void merge_array(int, int, int, int);

int arr_sort[MAX_SIZE];

int main() {
  int i;

  printf("Simple Merge Sort Example - Functions and Array\n");
  printf("\nEnter %d Elements for Sorting\n", MAX_SIZE);
  for (i = 0; i < MAX_SIZE; i++)
    scanf("%d", &arr_sort[i]);

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

  merge_sort(0, MAX_SIZE - 1);

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

}

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

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

void merge_array(int a, int b, int c, int d) {
  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];
}

Sample Output:

Simple Merge Sort Example - Functions and Array

Enter 5 Elements for Sorting
67
57
45
32
13

Your Data   :   67      57      45      32      13

Sorted Data :   13      32      45      57      67

------------------
(program exited with code: 0)

Related Pages

Learn the concept first, then study the code:

• Data Structures — Browse all Data Structures.
• C Array — Concept — sorting operates on array elements.
• Simple Bubble Sort Program in C — More in c sorting programs.
• Simple Bubble Sort Program using functions in C — More in c sorting programs.