COMP1927 - Merge Sort

Merge sort is a recursive divide and conquer sort. The list is halved repeatedly until each new halflist is only 1 element. The halflists are then merged back together.

The merging is done by keeping two counters, one for each halflist, and comparing the two current elements. The smallest is added to the merged list and the counter incremented.

This is repeated until all size mergedlists have been merged.

# Type

Non-Adaptive; It has to split down into individual items and merge back regardless of how pre-sorted it is

Stable/Non-Stable; Depends on implementation.

Non-In-Place; It can be made to be, but it usually isn't.

# Complexity

Merge sort is O(nlg(n)). We can prove this using recurrence relations. See the example there.

# Example

# Code

void mergesort (int temp[], int array[], int start, int end) { if (end > start) { int mid = (start + end)/2; mergesort(temp, array, start, mid); mergesort(temp, array, mid+1, end); int a = start; int b = mid+1; int insertCounter = start; // While each counter is still within the list for (insertCounter = start; (a <= mid) && (b <= end); insertCounter++) { // Find the smallest element // (i.e. compare the elements at current counter of each list) // Set the position we're up to in temp to be the smallest // At the same time increment the counter for that list if (array[a] < array[b]) { temp[insertCounter] = array[a]; a++; } else { temp[insertCounter] = array[b]; b++; } } // In this case b must have reached the end // Hence we just need to insert all of a into the sorted array while (a <= mid) { temp[insertCounter] = array[a]; insertCounter++; a++; } // In this case a must have reached the end // Hence we just need to insert all of b into the sorted array while (b <= end) { temp[insertCounter] = array[b]; insertCounter++; b++; } // Copy the sorted section in temp back to our array int i; for (i = start; i <= end; i++) { array[i] = temp[i]; } } else { // This is our base case // We do nothing and return in order to start the merging together } }

page revision: 6, last edited: 04 Oct 2011 02:00