Explore BrainMass
Share

Explore BrainMass

    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 Code1 (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 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)

                        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

    © BrainMass Inc. brainmass.com December 12, 2019, 11:44 am ad1c9bdddf