Merge sort is a sorting technique, which is based on comparison sorting algorithm, having complexity O(n log n). It is one of the types of stable sort, meaning, that in its implementation, input order of equal elements is preserved in the sorted output. It was invented by John von Neumann in 1945. Merge sort is a divide and conquer algorithm.
The concept of Merge Sort is based on the following principle:
Divide the unsorted list into 'n' sub-lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub-lists to produce new sub-lists until there is only 1 sub-list remaining. This will be the sorted list.
The concept of Merge Sort is based on the following principle:
Divide the unsorted list into 'n' sub-lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub-lists to produce new sub-lists until there is only 1 sub-list remaining. This will be the sorted list.
Algorithm for Merge Sort:
/* Double-Click To Select Code */ function merge_sort(list m) // if list size is 0 (empty) or 1, consider it sorted and return it // (using less than or equal prevents infinite recursion for a zero length m) if length(m) <= 1 return m // else list size is > 1, so split the list into two sublists var list left, right var integer middle = length(m) / 2 for each x in m before middle add x to left for each x in m after or equal middle add x to right // recursively call merge_sort() to further split each sublist // until sublist size is 1 left = merge_sort(left) right = merge_sort(right) // merge the sublists returned from prior calls to merge_sort() // and return the resulting merged sublist return merge(left, right)In this example, the merge function merges the Left and Right sublists.
/* Double-Click To Select Code */ function merge(left, right) var list result while length(left) > 0 or length(right) > 0 if length(left) > 0 and length(right) > 0 if first(left) <= first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) else if length(left) > 0 append first(left) to result left = rest(left) else if length(right) > 0 append first(right) to result right = rest(right) end while return result
Here is the C Code for Merge Sort:
/* Double-Click To Select Code */ #include <stdio.h> #include<conio.h> void mergesort(int arr[], int l, int h); void main(void) { int array[100],n,i = 0; clrscr(); printf("Enter the number of elements to be sorted: "); scanf("%d",&n); printf("\nEnter the elements to be sorted: \n"); for(i = 0 ; i < n ; i++ ) { printf("\tArray[%d] = ",i); scanf("%d",&array[i]); } printf("\nBefore Mergesort:"); //Array Before Mergesort for(i = 0; i < n; i++) { printf("%4d", array[i]); } printf("\n"); mergesort(array, 0, n - 1); printf("\nAfter Mergesort:"); //Array After Mergesort for(i = 0; i < n; i++) { printf("%4d", array[i]); } printf("\n"); getch(); } void mergesort(int arr[], int l, int h) { int i = 0; int length = h - l + 1; int pivot = 0; int merge1 = 0; int merge2 = 0; int temp[100]; if(l == h) return; pivot = (l + h) / 2; mergesort(arr, l, pivot); mergesort(arr, pivot + 1, h); for(i = 0; i < length; i++) { temp[i] = arr[l + i]; } merge1 = 0; merge2 = pivot - l + 1; for(i = 0; i < length; i++) { if(merge2 <= h - l) { if(merge1 <= pivot - l) { if(temp[merge1] > temp[merge2]) { arr[i + l] = temp[merge2++]; } else { arr[i + l] = temp[merge1++]; } } else { arr[i + l] = temp[merge2++]; } } else { arr[i + l] = temp[merge1++]; } } }
Output of Program:
Please Comment If You Liked This Post !!
This article uses material from the Wikipedia article Merge Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0
Do you like this post? Please link back to this article by copying one of the codes below.
URL: HTML link code: Forum link code: