Merge SortingOften, computer programs need to traverse a list to find data that is relevant to the application. It makes life easier when the list, array, etc... is sorted. So far bubble, insertion, and other sort/search methods have been covered. However, there is yet another that is one of the three "foundations" (in my opinion) of search and/or sorting techniques. Merge sorting uses more memory then other sorting methods (due to the duplicate structure needed for sorting); it is not guarenteed O(n) efficiency, but more on that later.
What is it?Merge sorting takes one array (in the below example code), copies it into a duplicate array, divides the array in half and sorts each independently, uses recursion to sort the values, and then puts the sorted array back into the original data structure. The idea is that a single call to a subset function of the initial mergeSort() function allows the program to take over without further manipulation by the user or programmer. I feel that it is a component of encapsulation; once it is written, it will hardly ever need retooling unless a more specific procedure is needed or optimization for large sets of data (then again, what doesn't need more optimization these days?)
Example:In the code we have a predefined array of integers (it is extremely easy to have user defined input, etc...)
cpp
int arrayOne[5] = {65, 72, 105, 55, 2}; //initial array that will eventually be displayed as sorted
int arrayTwo[5]; //empty array to use for sorting
mergeSort(arrayOne, arrayTwo, 5); //params, first array, duplicate, and size of array, can be dynamic
Let's go step by step through the calls:
65, 72, 105, 55, 2 is currently the original array
CODE
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
At this point all the "main" call does is define the limit of the array (remember an array is 0 to max - 1) and passes the information along to step one of the merge sort recursion "tree". In the next mini segment we will divide and conquer:
CODE
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, (mid+1), right);
merge(numbers, temp, left, (mid+1), right);
}
}
We give it the original array, duplicate one, and the left and right extremes (zero and max -1). Right should always be greater then left (starting out initially). We then proceed to divide the array in "half" or as approx. to half evenly as possible. We then recursively call m_sort() to sort the array. After sorting, the two halves are then "merged" to create a "whole" array:
CODE
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos += 1;
left += 1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos += 1;
mid += 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left += 1;
tmp_pos += 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid += 1;
tmp_pos += 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right -= 1;
}
}
The combination here is basic and be taken further based on data structures or even custom classes you create! This outline illustrates the basic idea behind merge sorting. The merge is done each iteration through m_sort().
Here is a list rundown of how a merge sort works if you don't want to read all of the above:
1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sub-lists of about half the size.
3. Sort each sub-list recursively by re-applying merge sort.
4. Merge the two sub-lists back into one sorted list.
Numerical rundown for a visual aid:
65, 72, 105, 55, 2 --original array
65, 72, 105, 55, 2 --duplicated into temp array
65, 72, 105 and
55, 2 -- array divided
65, 72 and
105 and
55, 2 -- further division for comparison
65, 72, 105 2, 55 --comparisons made, swaps executed, merged
2, 55, 65, 72, 105 -- final merged result, each step is a simple repeat of the prior ones
Efficiency:Average case:O(n *log n), not great, but this sorting method has practical application in generally sequential data storage and the like.
Worst case:(n *log n + n O(log n)), it can get messy.
Best case:Unfortunately is is often O(n* log n)
Full Code can be found
HEREGood news for programmers is that in modern systems location of data in memory contributes
greatly to the speed/efficiency of this algorithm as a whole. Sequential data storage allows this sorting method to soar past quick and bubble sorting. Quicksort is regarded as the fastest of the general sorting methods, but Merge Sorting is a stable sorting method if implemented correctly. Group the data in memory together if possible and this sorting method will be well worth the time to implement/learn. Attached is a picture that does an excellent job of illustrating what exactly is taking place during merge sorting. Happy Coding!
This post has been edited by KYA: 18 Jul, 2008 - 08:04 AM
Merge Sorting: A Look With Recursion, Sort data using merge techniques
17 Jul, 2008 - 06:51 PM
|