Merge Sort

goo.gl/d1wyx

Merge Sort Points:

  Divide and Conquer (and combine):

 Divide unsorted list into 2 sub lists. Sort sub lists recursively until the list size is of 1.
 Then it returns itself.

Combine the sub-lists back into form the main list (with sorted items.)

Analysis: O(n log n) Average and Worst.

Although it is O(n log n) it requires a lot of space for merges.

Best done as external sort. From wikipedia

An external merge sort is practical to run using disk or tape drives when the data to be sorted is too large to fit into memory. External sorting explains how merge sort is implemented with disk drives. A typical tape drive sort uses four tape drives. All I/O is sequential (except for rewinds at the end of each pass). A minimal implementation can get by with just 2 record buffers and a few program variables.