Merge sort facts for kids

Merge sort (or mergesort) is an divide and conquer algorithm for sorting a list of elements. John von Neumann first presented it in 1945. The algorithm is pretty simple:

• Divide the list of elements into two lists, of half the size of the original list
• Apply the algorithm to each of the two lists
• Merge the two sorted lists together.

This is the same as with quicksort, developed in 1960. The difference is that with merge sort, dividing the lists is trivial, and merging them together isn't. With quicksort, dividing the lists is more complex, but the merging step is trivial. Also note that merge sort is a stable sorting algorithm, while quicksort isn't.

Images for kids

• 

  Merge sort type algorithms allowed large data sets to be sorted on early computers that had small random access memories by modern standards. Records were stored on magnetic tape and processed on banks of magnetic tape drives, such as these IBM 729s.

• 

  Tiled merge sort applied to an array of random integers. The horizontal axis is the array index and the vertical axis is the integer.