Merge Sort

Simon: What happens if they board us?

Zoë: If they take the ship, they will rape us to death, eat our flesh, and sew our skins in to their clothing, and if we're very, very lucky, they’ll do it in that order.

From "Serenity", episode 11 of Firefly

Merge Sort is a comparison-based sorting algorithm invented by John von Neumann in 1945.

Conceptually, a merge sort works as follows:

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

Needless to say, this algorithm is implemented using a design pardigm called Divide-and-Conquer.

The algorithm's complexity is O(n lg n) (loglinear). Kirk out!