After a long week of studying and finals, here is the next tutorial in the sorting series. For this week, I'm going to cover the merge sort. The merge sort is another recursive sort.
The merge sort is is simpler to understand and code than the quick sort is. The merge sort works by recursively splitting a list in half until the split halves only have one element in them, then recombining the lists, sorting as you revurse back up. Here's the code for those who like to look at coding examples.
| CODE |
void MergeSort(int *elems, int numElems)
{
MergeSortRec(elems, 0, numElems - 1);
}
void MergeSortRec(int *elems, int first, int last)
{
if(first >= last)
return;
int mid; // Will be index of the middle element
mid = (first + last)/2;
// split the array into it's 2 halves
MergeSort(elems,first,mid);
MergeSort(elems, mid+1, last);
// Now merge the two halves
int *temp;
tempArray = (int*)malloc(sizeof(int) * (last - first + 1));
// Initialize the local indices of the subarrays
int first1 = first;
int last1 = mid;
int first2 = mid + 1;
int last2 = last;
int index = first1; // Next available location in temp array
// While both subarrays are not empty, copy
// the smaller first element of the two subarrays
// into the temporary array
while((first1 <= last1) && (first2 <= last2))
{
// if the element in the first subarray is smaller
if (elems[first1] <= elems[first2])
{ // take an element from the first subarray
tempArray[index] = elems[first1];
++first1;
}
else
{ // otherwise, take an element from the second subarray
tempArray[index] = elems[first2];
++first2;
}
++index
}
// First finish off the first subarray:
while(first1 <= last1)
{
tempArray[index] = elems[first1];
++first1;
++index;
}
// Now finish off the second subarray:
while(first2 <= last2)
{
tempArray[index] = elems[first2];
++index;
++first2;
}
// Now copy back from the temporary array to the original one
for (index = first; index<=last; index++)
A[Index] = tempArray[Index];
free(tempArray);
} // end MergeSort
|
The code for the merge sort can be looked at in two parts, the splitting part and the merging part. The merging part is where the sorting actually takes place. I used malloc to dynamically allocate memory for a temporary array. Sorry to those who like STL, I still haven't had a chance to check it out.
Now onto other matters. The sort has the same speed as most other recursive sorts, O(n log n). This makes it among the faster of the sorts. It's stability, though, is unlike most other recursive arrays. This sort actually is stable. So, what's the downside of the merge sort? It's memory footprint.
The merge sort takes large amounts of memory to run. This makes it unsutable for large amounts of data or for computers with very little spare memory. This is because of the temporary array required to remake the list.
That's it for the merge sort. Next week I'm going to cover the radix sort, a sort great for sorting strings. It'll be my last tutorial of this series and I'll also be covering more in depth the when and why of choosing a sort. I'll be starting another series on data structures shortly thereafter. Just as a heads up, know how to use and be comfortable with pointers.
Hey BloodGhst, you forgotten something? (hint* [CODE] *hint ;))
Oops. Thanks for pointing that out. All fixed up.
