Mergesort

Implementation

Mergesort (or 'merge sort'), invented in 1945 by John von Neumann, takes a 'divide and conqueror' approach to sorting by splitting an array into individual elements which are trivially sorted and then piecing them back together in ascending order. The array is split up by dividing the length of the array by two (taking the floor of that) and making a sub-array of each part. The reassembling method depends on which first element of each of the two sub-arrays being reassembled is bigger. If the left array's first element is bigger than the right's, they will be reassembled using a merge function but if the right's is bigger, or they are equal, the right array can simply be appended onto the end of the left one.

Here is the pseudocode that specifies this algorithm, taken from Rosetta Code¹ (m is the array to be sorted):

function mergesort(m)

var list left, right, result

  if length(m) ≤ 1

      return m

  else

      var middle = length(m) / 2

      for each x in m up to middle - 1

          add x to left

      for each x in m at and after middle

          add x to right

      left = mergesort(left)

      right = mergesort(right)

      if last(left) ≤ first(right)

          append right to left

          return left

      result = merge(left, right)

      return result

Below you can see it in action using the example mergesort([5, 3, 7, 1, 0, 8, 5]):

The < and > in the gif above mark whether the first element of the left sub-array is less than or greater than that of the right sub-array. Append can be understood immediately but the merge operation is specific to this sorting function. It is done by comparing the first element of each subarray in turn until one is exhausted and the other may be appended on the end. The following is pseudocode for the merge function¹:

function merge(left,right)

  var list result

  while length(left) > 0 and length(right) > 0

      if first(left) ≤ first(right)

          append first(left) to result

          left = rest(left)

      else

          append first(right) to result

          right = rest(right)

  if length(left) > 0

      append rest(left) to result

  if length(right) > 0

      append rest(right) to result

  return result

See below for an example of this implementation using the first instance described in our example, merging [5] with [3, 7]:

Performance

Mergesort operates, on average and in worst-case, in O(n log n) time. In addition, it can take advantage of parts of a list/array that are already sorted and so can run faster with these sorts of input. It is also what is known as a stable sort which means the order of elements with the same value is preserved (so in the above example, if some other information were attached to the 5s, they would be in the same order in the output of mergesort as they were going in). This makes it preferable to quicksort in some cases as it performs less comparisons than its fellow O(n log n) sorting algorithm, though it does typically takes more space in memory to perform.

References:

1. Pseudocode from Rosetta Code

Implementation

Performance

BrainMass