MergeSort

MergeSort is a divide-and-conquer algorithm that recursively sorts two halves of an array and merges them to form a fully sorted end result. In other words, to sort a sequence, we find the middle point, sort the first half, sort the second half, and finally merge both halves:

def mergeSort(array, start, end):
    if end - start > 1:
        middle = (start + end) / 2
        mergeSort(array, start, middle)
        mergeSort(array, middle, end)
        merge(array, start, middle, middle, end)

The merging of the two halves is done by inserting elements of the second half into the first half. The second half keeps shrinking in size until we are done:

def merge(array, left, leftEnd, right, rightEnd):
    while left<leftEnd and right<rightEnd:
        if array[left] > array[right]:
            array.insert(left, array.pop(right))
            right += 1
            leftEnd += 1
        else:
            left += 1

Executing the above implementation on 40 random numbers produces the following result:

This implementation is a stable sort. Elements of equal value remain in their original sort order.


Check out more algorithm visualizations at PyAlgoViz.

---

Python code styled as tango by hilite.me with border:1px solid #ddd;padding:11px 7px;