# merge sort in c

**Merger Sort**

**Merger Sort**

*Merge sort is a divide and conquer based sorting algorithm.The complexity of the merge sort algorithm is O(NlogN). most of the implementation of merge sort is stable sort. A sorting algorithm is said to be stable if it is maintaining the relative order of equal elements of input set. Below is the basic approach of merge sort.*

*1)Divide the array repeatedly into two halves*

*2)Stop dividing when there is single element left. By*

*fact, single element is already sorted.*

*3)Merges two already sorted sub arrays into one*

*The above figure shows the approach for merge sort. (image source from wikipedia). suppose we have list { 38, 27, 43, 3, 9, 82, 10 }; as from above figure. below is sample code in c which implements the merge sort approach.
*

#include<stdio.h> void print (int *arr, int size); void merge (int *arr, int m, int r); void split (int *arr, int length) { if (length == 1) return; int middle = length / 2; int remaining = length - middle; split (arr, middle); // split first half split (arr + middle, remaining); // split 2nd half merge(arr,middle,remaining); //merge } void merge (int *arr, int m, int r) { int temp[m + r]; int i = 0, j = 0; while (i + j < m + r) { if (i < m && arr[i] <= arr[m + j] || i < m && j >= r) temp[i + j] = arr[i++]; if (j < r && arr[m + j] < arr[i] || j < r && i >= m) temp[i + j] = arr[m + j++]; } int k; for (k = 0; k < m + r; k++) arr[k] = temp[k]; } int main () { int arr[] = { 38, 27, 43, 3, 9, 82, 10 }; int length = sizeof (arr) / sizeof (arr[0]); /* print array before sort */ printf ("The unsorted list is:\n"); print (arr, length); /* split the list */ split (arr, length); printf ("The sorted list is:\n"); print (arr, length); return 0; } void print (int *arr, int size) { int i; for (i = 0; i < size; i++) printf ("%d ", arr[i]); printf ("\n"); return; }

Ref:

## Leave a Reply