Explore BrainMass



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 Code1 (m is the array to be sorted):

function mergesort(m) 

          var list left, right, result

          if length(m) ≤ 1

                    return m


                    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 function1:

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)


                              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]:


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.



1. Pseudocode from Rosetta Code