Merge Sort and its Implementation in ‘C’

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.

Merge sort animation.

Merge sort animation. Courtesy: Wikipedia.org

Complexities

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 )

Input:

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

Sample Input

3
5 4 7 9 3 1
3 4 5 5
4 6 10 6 7

Sample Output

1 3 4 7 9
4 5 5 
6 6 7 10

Code

Brief explanation is given in the gist.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s