## Friday, December 16, 2016

### 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;