Sorting

Put elements of a collection into a defined order, the building block behind searching and many other algorithms.

Concepts

Repeatedly swap neighboring out-of-order elements until the whole list is sorted, simple but slow on large lists.

Split the list in half, sort each half, then merge them back together in order, giving reliable O(n log n) time.

Pick a pivot, move smaller elements left and larger ones right, then repeat on each side to sort in place.

Build the sorted list one element at a time, inserting each new element into its correct position as you go.

Repeatedly find the smallest remaining element and move it into place, simple to write but slow on large lists.

Build a heap from the list, then repeatedly pull out the largest element to sort in place in O(n log n).

Count how many times each value appears, then rebuild the list in order, sorting in O(n) when values fall in a small range.