Summary

Putting things in order is a very fundamental problem that has been solved in many different ways, varying in aspects such as worst-case runtime complexity, memory required, the relative order of equal elements (stability), as well as overall strategies. A few fundamental approaches were presented in this chapter.

Bubble sort is one of the simplest algorithms to implement, but it comes at a high runtime cost, with a worst-case behavior of O(n²). This is due to the fact that it simply swaps elements based on a nested loop, which makes elements "bubble up" to either end of the collection.

Shell sort can be seen as an improved version of bubble sort, with a major upside: it does not start off by swapping neighbors. Instead, there is a gap that elements are compared and swapped across, covering a greater distance. This gap size changes with every round that shows worst-case runtime complexities of O(n²) for the original scheme to O(n log n) in the fastest variant. In fact, the runtime...