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