Merge sort follows the divide and rule policy. This algorithm divides the array of N elements into separate smaller arrays and then sorts & rejoins the divided arrays one by one with each other to form the resultant array. Merge sort uses recursion to the achieve division and merge process.
Merge sort algorithm
To explain this sorting technique we take an array elements containing N elements.
Two variables "upper" and "lower" stores the upper limit and the lower limit. Starting the process, lower limit starts with the position of first element in the array which is generally zero/0. Upper limit starts with the position of the last element, generally (N-1)th element. The middle position of the array is obtained by adding upper and lower and dividing the result by 2. The obtained position is used to divide the array into two sub arrays. The procedure is followed repeatedly on the sub arrays and the subsequent sub arrays until upper equals lower. This happens when each sub array contains one element each, i.e. when the array has been divided into N sub arrays.
This process can be better explained with an example:
Let an array elements contain the following elements:
34 45 89 23 38 76 12 28
The length of the array is 8, so N = 8. Thus lower = 0 (since position of elements in array starts from 0) and upper=s-1=7.
Thus the array will be split from the middle, i.e. (0+7)/2=3 (element at 4th position). The array becomes:
[34 45 89 23] [38 76 12 28] ( represents a sub array)
Now each sub array will be considered an individual array and the procedure will be applied to each sub array again.
The left sub array has four elements and so, lower=0 and upper=3. Thus middle point occurs at 1 (position of second element)
The right sub array also has four elements and so, lower=4 and upper=7. Thus the middle point occurs at 5 (position of 6th element)
Thus the sub arrays get divided and the result becomes:
[34 45] [89 23] [38 76] [12 28]
This process is repeated till all sub arrays contain 1 element each.
       
The s divided arrays are joined together to form the complete array and the elements are sorted at the same time. This is done by sorting the elements of two arrays while joining them in a third array.
This process can be better explained with an example:
Let us take the divided array shown above:
       
The combining procedure takes place as follows:
The single array obtained at the end is the sorted array.
The mergesort algorithm generally contains two distinct methods:
mergesort(elements,lower,upper):This method shares its name with the sorting technique and is generally used to split the array of N elements into N sub arrays each containing 1 element. This is done by using a recursive function for most convenience.
An algorithm for the method is as follows:Check if upper bound is greater than lower bound else exit Calculate new middle position and divide the array by two halves Call merge sort again for lower half Call merge sort again for upper half Now merge the two halves of the array
merge(elements,lower,mid,mid+1,upper):This method joins the two separated arrays into a temporary array before transferring the elements to the original array. The method also sorts the array while joining them.
Let us consider an array elements with s elements. Let us also consider that the array has been split into two sub arrays at the middle position.
The array elements has been sent to the merge() method along with the position of the first element and the position of the last element of both the sub arrays. Two variables p and q(initialized to the position of the first element of first sub array and second sub array respectively) are used to point to the elements in the arrays.
Now the elements in the two sub arrays are put into a third temporary array D in the following manner:
- The element at p and q are compared.
- If element at p matches the condition, the element is put into D and p is incremented by 1.
- If element at q matches the condition, the element is put into D and q is incremented by 1.
- This is continued till either p or q reaches the last element in its array.
- If p reaches its end, the remaining elements in the array pointed by q is put in D or vice versa.
(The condition refers to elements being greater or lesser than each other.)
After all the elements in the sub arrays have been sorted in D, the elements are put back into the sub arrays in the order it is present in D.
Let us take an example to better understand this method:
Let an array elements have 8 elements:
23 34 45 89 12 28 38 76
Let it be split up into two sub arrays:
Left sub array: [23 34 45 89]
Right sub array: [12 28 38 76]
p will point to the beginning of left sub array while q will point to the beginning of the second sub array.
The elements will be stored in D in the following manner:(considering elements[p] < elements[q] as condition)
P q D [23 34 45 89] [12 28 38 76]*  P q D [23 34 45 89] [12 28 38 76]  P q D [23 34 45 89] [12 28 38 76]*  P q D [23 34 45 89] [12 28 38 76] [12 23] P q D [23 34 45 89] [12 28 38 76]* [12 23] P q D [23 34 45 89] [12 28 38 76] [12 23 28] P q D [23 34 45 89] [12 28 38 76]* [12 23 28] P q D [23 34 45 89] [12 28 38 76] [12 23 28 34] P q D [23 34 45 89] [12 28 38 76]* [12 23 28 34] P q D [23 34 45 89] [12 28 38 76] [12 23 28 34 38] P q D [23 34 45 89] [12 28 38 76]* [12 23 28 34 38] P q D [23 34 45 89] [12 28 38 76] [12 23 28 34 38 45] P q D [23 34 45 89] [12 28 38 76]* [12 23 28 34 38 45] P q D [23 34 45 89] [12 28 38 76] [12 23 28 34 38 45 76] * indicates elements being pointed by p and q are being compared
Since q reaches limit, the remaining element of p is transferred to D. Thus the elements of D are:
[12 23 28 34 38 45 76 89]
These elements are put into the sub arrays in the order it is present in D.
An algorithm for this method is as follows:
Mergesort using array:
Mergesort using linked list:
Mergesort may be done using array or linked list. Fully working codes of mergesort using array and linked list has been given below. The programs have been written in C.
About our authors: Team EQA
You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.
Learn on Youtube