Sorting, and why some ways are hopeless

Sorting is where the difference between O(n²) and O(n log n) stops being theory.

The three simple ones, all O(n²)

Bubble sort repeatedly swaps neighbours that are in the wrong order. Selection sort repeatedly finds the smallest and puts it in place. Insertion sort takes each item and slides it back into the sorted part.

All three are nested loops, so all three are quadratic. They differ in the constants and in one useful property: insertion sort is O(n) on data that is already nearly sorted, which is why real implementations use it for small or almost-ordered chunks.

The two good ones

Merge sort. Split in half, sort each half, merge the two sorted halves. Splitting gives log n levels, merging each level costs n, so O(n log n) always, best case and worst. It needs O(n) extra space for the merge, and it is stable: equal items keep their original order.

Quick sort. Pick a pivot, put smaller on the left and larger on the right, recurse. O(n log n) on average, and O(n²) if the pivot is always the worst choice, which happens on already-sorted data with a naive pivot. It needs no extra array, which is why it is usually faster in practice despite the worse worst case.

What "stable" buys you

Sort employees by name, then by department. With a stable sort, people within a department are still in name order. With an unstable one, that ordering is lost, and there is no way to get it back except sorting again.

What you will actually use

sorted() in Python is Timsort: merge sort and insertion sort combined, stable, and O(n) on already-sorted input. Java's Arrays.sort uses quicksort for primitives and Timsort for objects, for exactly the stability reason above.