One fundamental strategy in battle, as well as in sorting collections, is to divide and conquer. Merge sort does exactly that, by splitting the collection in half recursively until only a single element remains. The merging operation can then put these single elements together in the correct order with the benefit of working with presorted collections.
What this does is reduce the problem size (in other words, the number of elements in the collection) to more manageable chunks that come presorted for easier comparison, resulting in a worst case runtime complexity of O(n log n). The following diagram shows the split and merge process (note that comparing and ordering only starts at the merge step):
There are various implementations of this principle: bottom up, top down, using blocks, and other variations. In fact, as of 2018, Rust's default sorting algorithm is Timsort, a stable, hybrid algorithm that combines insertion sort (up until a certain size) with merge sort.
...
