Conceptually, merge sort works as follows :
If the list to be sorted is longer than one item:
Merge sort has an average and worstcase performance of O(n log(n)). This means that it often needs to make fewer comparisons than quicksort. However, the algorithm's overhead is slightly higher than quicksort's, and, depending on the data structure to be sorted, may take more memory (though this is becoming less and less of a consideration). It is also much more efficient than quicksort if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp where sequentially accessed data structures are very common. Unlike quicksort, merge sort is a stable sort.
Mergesort is so sequential that it's practical to run it on tapes if you have four tape drives. It works as follows:
On tape drives that can run both backwards and forwards, you can run merge passes in both directions, avoiding any time rewinding.
For the same reason it is also very useful for sorting data on disk that is too big to fit into primary memory.
This might seem to be of historical interest only, but on modern computers, locality of reference is of paramount importance in software optimization, because we have deep memory hierarchies[?]. This might change if fast memory becomes very cheap again, or if exotic architectures like the Tera MTA[?] become commonplace.
Here's a terrible implementation of mergesort in Python:
def merge(array, start1, end1, start2, end2, output, outstart, cmp): """Merge two sorted sequences into a new sorted sequence. Takes two sorted sequences 'array[start1:end1]' and 'array[start2:end2]' and merges them into a new sorted sequence, which it places in the array 'output', starting at 'outstart'. """ while start1 != end1 or start2 != end2: if start2 == end2 or (start1 != end1 and not cmp(array[start1], array[start2])): output[outstart] = array[start1] start1 = start1 + 1 else: output[outstart] = array[start2] start2 = start2 + 1 outstart = outstart + 1 def mergesort(array, cmp=lambda x, y: x > y, scratch=None, start=None, end=None): """The fastest stable sort for large data sets.""" if scratch is None: scratch = [0] * len(array) if start is None: start = 0 if end is None: end = len(array) if end  start > 1: middle = (start + end) / 2 mergesort(array, cmp, scratch, start, middle) mergesort(array, cmp, scratch, middle, end) merge(array, start, middle, middle, end, scratch, start, cmp) array[start:end] = scratch[start:end]
Here is some C code that does merge sort. It assumes that two arrays, v1 and v2 have been allocated to be of size n/2; they will be used for the merging operation: (from PD [lecture notes (http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture2)])
void merge (float [], int, int, int); /* sort the (sub)array v from start to end */ void merge_sort (float v[], int start, int end) { int middle; /* the middle of the subarray */ /* no elements to sort */ if (start == end) return; /* one element; already sorted! */ if (start == end  1) return; /* find the middle of the array, splitting it into two subarrays */ middle = (start + end) / 2; /* sort the subarray from start..middle */ merge_sort (v, start, middle); /* sort the subarray from middle..end */ merge_sort (v, middle, end); /* merge the two sorted halves */ merge (v, start, middle, end); } /* merge the subarray v[start..middle] with v[middle..end], placing the * result back into v. */ void merge (float v[], int start, int middle, int end) { int v1_n, v2_n, v1_index, v2_index, i; /* number of elements in first subarray */ v1_n = middle  start; /* number of elements in second subarray */ v2_n = end  middle; /* fill v1 and v2 with the elements of the first and second * subarrays, respectively */ for (i=0; i<v1_n; i++) v1[i] = v[start + i]; for (i=0; i<v2_n; i++) v2[i] = v[middle + i]; /* v1_index and v2_index will index into v1 and v2, respectively... */ v1_index = 0; v2_index = 0; /* ... as we pick elements from one or the other to place back * into v */ for (i=0; (v1_index < v1_n) && (v2_index < v2_n); i++) { /* current v1 element less than current v2 element? */ if (v1[v1_index] <= v2[v2_index]) /* if so, this element belong as next in v */ v[start + i] = v1[v1_index++]; else /* otherwise, the element from v2 belongs there */ v[start + i] = v2[v2_index++]; } /* clean up; either v1 or v2 may have stuff left in it */ for (; v1_index < v1_n; i++) v[start + i] = v1[v1_index++]; for (; v2_index < v2_n; i++) v[start + i] = v2[v2_index++]; }
Here is a not very good, but clear, version in the functional programming language Haskell. (It can be improved by techniques such as tupling[?] for efficiency)
merge :: Ord a => [a] > [a] merge [] list = list merge list [] = list merge (h1:t1) (h2:t2) = if h1<=h2 then h1: (merge t1 (h2:t2)) else h2:(merge (h1:t1) t2)
mergesort :: Ord a => [a] > [a] mergesort [] = [] mergesort [x] = [x] mergesort list = merge (take nn list) (drop nn list) where nn = (length list) `div` 2
Search Encyclopedia

Featured Article
