Sorting algorithms

• Quick Sortn log n

  Quick Sort picks a pivot, splits the list into smaller and larger halves, and sorts each half the same way.

• Merge Sortn log n

  Merge Sort splits the list in half, sorts both halves, then merges the two sorted halves into one.

• Heap Sortn log n

  Heap Sort builds a max-heap from the list, then repeatedly moves the largest value to the end.

• Shell Sortn^1.5

  Shell Sort runs insertion sort on elements far apart first, then on closer and closer elements.

• Insertion Sortn²

  Insertion Sort takes each value in turn and slides it left until it sits in the right place.

• Selection Sortn²

  Selection Sort finds the smallest remaining value and swaps it to the front, again and again.

• Bubble Sortn²

  Bubble Sort walks through the list swapping neighbours that are out of order, until a pass makes no swaps.

• Cocktail Shaker Sortn²

  Cocktail Shaker Sort is Bubble Sort that runs forwards and then backwards, so small values move quickly too.

• Comb Sortn²/2^p

  Comb Sort is Bubble Sort with a shrinking gap: it compares values far apart first, then closer ones.

• Gnome Sortn²

  Gnome Sort steps forward while neighbours are in order and steps back, swapping, when they aren't.

• Odd-Even Sortn²

  Odd-Even Sort alternates between comparing odd-indexed pairs and even-indexed pairs of neighbours.

• Cycle Sortn²

  Cycle Sort writes every value directly to its final position, using the fewest possible writes.

• Pancake Sortn²

  Pancake Sort only reverses prefixes of the list: flip the largest value to the top, then flip it into place.

• Radix Sortn·k

  Radix Sort sorts numbers digit by digit, from the least significant digit up, without comparing values.

• Counting Sortn + k

  Counting Sort counts how many times each value occurs, then writes the values back in order.

• Bucket Sortn + k

  Bucket Sort spreads values into buckets by range, sorts each bucket, then joins them.

• Tim Sortn log n

  Tim Sort sorts short runs with Insertion Sort, then merges the runs like Merge Sort.

• Bitonic Sortn log² n

  Bitonic Sort builds rising-then-falling sequences and merges them with a fixed network of comparisons.

• Gravity SortS

  Gravity Sort (bead sort) drops beads on rods like an abacus, so each row settles to its sorted length.

• Stooge Sortn^2.71

  Stooge Sort recursively sorts the first two thirds, the last two thirds, then the first two thirds again.

• Bogo Sortn·n!

  Bogo Sort shuffles the list at random and checks if it's sorted. Then it shuffles again.

• Keep Bogo Sortn²

  Keep Bogo Sort shuffles at random, but every element that lands in the right spot stays there.