The Complete Rust Programming Reference Guide

Merge sort

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 ...