Sorting Algorithms | Knowledge Base by Andrii Sonsiadlo

📄️Overview

Sorting is the most-studied problem in the field, and not because arranging things in order is

Bubble sort repeatedly walks the array comparing adjacent pairs and swapping them when they are out

Selection sort divides the array into a sorted prefix and an unsorted remainder. Each round it scans

Insertion sort builds the sorted result one element at a time, taking the next element and sliding it

Mergesort splits the array in half, sorts each half recursively, and merges the two sorted halves

Quicksort picks an element as the pivot, rearranges the array so that everything smaller sits to

Heapsort is selection sort with a better way of selecting. Selection sort scans

Every comparison sort on this page's siblings is bound below by $Ω(n \log n)$ — a fact proved by a

Finding the k-th smallest element does not require sorting the whole array. Sorting throws away no

Every algorithm on the earlier pages of this folder assumes the whole array fits in memory, so any two

In almost every situation the correct answer is call your language's built-in sort. Those

This page is a reference, not a tutorial — each algorithm's own page derives the bound it gets here.