From chaos to order
There are many sorting algorithms (and their individual variations), each with their individual characteristics. Since it is impossible to cover every algorithm in a single chapter, and considering their limited usefulness, this chapter covers a selected few.
The selection should show the different strategies that are common in sorting a collection of items, many of which have been implemented in various libraries across different languages. Since many of you will never implement any sorting algorithms for productive use, this section is supposed to familiarize you with what's behind the scenes when a call to mycollection.sort() is issued, and why this could take a surprising amount of time.
Sorting algorithms fall into a group on each of these properties:
- Stable: Maintains a relative order when comparing equal values
- Hybrid: Combines two or more sorting approaches (for example, by collection length)
- In-place: Uses indices instead of full copies for passing collections around...
