The Merge sort reference article from the English Wikipedia on 24-Jul-2004
(provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Merge sort

For thoughtful child sponsors
In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order. It is a particularly good example of the divide and conquer algorithmic paradigm.

Conceptually, merge sort works as follows :

If the list to be sorted is longer than one item:

  1. Divide the unsorted list into two sublists of about half the size
  2. Sort each of the two sublists
  3. Merge the two sorted sublists back into one sorted list.

Merge sort has an average and worst-case 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 for commonly available hardware and typical data). 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.

Merge sort is so inherently sequential it's practical to run it using slow tape drives as input and output devices. It requires very little memory, and the memory required does not change with the number of data elements. If you have four tape drives, it works as follows:

  1. divide the data to be sorted in half and put half on each of two tapes
  2. merge individual pairs of records from the two tapes; write two-record chunks alternately to each of the two output tapes
  3. merge the two-record chunks from the two output tapes into four-record chunks; write these alternately to the original two input tapes
  4. merge the four-record chunks into eight-record chunks; write these alternately to the original two output tapes
  5. repeat until you have one chunk containing all the data, sorted --- that is, for lg n passes, where n is the number of records.

On tape drives that can run both backwards and forwards, you can run merge passes in both directions, avoiding rewind time.

For the same reason it is also very useful for sorting data on disk that is too large to fit entirely 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 multi-level memory hierarchies are used. In some sense, main RAM can be seen as a slow tape drive, level 3 cache memory as a slightly faster one, level 2 cache memory as faster still, and so on. In some circumstances, cache reloading might impose unacceptable overhead and a carefully crafted merge sort could have considerable running time improvement. This opportunity might change if fast memory becomes very cheap again, or if exotic architectures like the Tera MTA become commonplace.

Designing a merge sort to perform optimally often requires adjustment to available hardware, eg. number of tape drives, or size and speed of the relevant cache memory levels. Here is some C code that does a simple 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])


void merge_sort(float [], int, int);
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;




/* create v1 and v2 subarrays */



float v1[v1_n];



float v2[v2_n];




/* fill v1 and v2 with the elements of the first and second



 * subarrays, respectively



 */



for (i=0; i

for (i=0; 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++];


}



External Resources