Merge sort is an advanced sorting algorithm, derived from divide and conquer algorithmic paradigm. It works as follows:
1. Divide unsorted array into N sub-arrays, each containing one element. (which is sorted already)
2. Repeatedly merge these sub-arrays to produce sorted new ones until only 1 sub-array is left-out, this is the required sorted array.
Look at the following animation for clear understanding.
Time complexity : O( N log N -- N log N -- N log N ) [Best -- Average -- Worst] Memory : O(N) # auxiliary i.e. apart from storing input array Stable : Yes i.e. doesn't change relative order of elements with same key # N being the number of elements in the array
You can read complexities of other popular sorting algorithms here.
Usage and Applications
As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Merge sort is often the best choice for sorting linked lists. Used to find inversion count of an array.
Bottom Line: Typically, default sort implementation for most of the languages is either Mergesort or Quicksort.
Implementation in C:
Question: Sort an array of integers in increasing order using merge sort algorithm (format similar to most of the online programming contests )
First line of the input contains T, number of test cases
Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.
Output: Sorted array
3 5 4 7 9 3 1 3 4 5 5 4 6 10 6 7
1 3 4 7 9 4 5 5 6 6 7 10
Brief explanation is given in the gist.