Sorting Algorithms in TheAlgorithms/Python

Insertion sort imagines the list as two regions: a sorted prefix on the left and an unsorted suffix on the right. For each element in the unsorted region, the algorithm saves the value in insert_value and shifts all larger sorted-region elements one position right, creating a gap. When the correct gap is found the value drops in. The key distinction from bubble sort is that this is a shift operation, not a swap: only one element moves per iteration of the while loop. That halves the number of write operations on lists that are already mostly sorted. See the deeper tour for full doctest analysis and comparisons with Python's built-in timsort, which uses insertion sort for small subranges.

Selection sort's trade-off runs in the opposite direction from insertion sort: it does the maximum number of comparisons but the minimum number of writes. The inner loop on lines 22-24 scans the entire unsorted region to find the index of the smallest remaining element. After the scan, exactly one swap moves that element to position i. The guard on line 25 skips the swap when the element is already in place, saving one write. In O(n squared) comparison count, selection sort matches bubble sort, but it never does more than O(n) swaps total across the full sort. That matters when writes are expensive, such as in flash memory. The deeper tour covers the full file.

Merge sort separates the concern of splitting from the concern of combining. The outer merge_sort handles splitting: if the collection has more than one element it computes a midpoint and recurses on both halves. The inner merge function handles combining: two already-sorted lists are walked in lockstep, and the smaller of the two leading elements is popped and appended to result each iteration. When one list empties, extend drains the other in order. The pop(0) call is O(n) on Python lists, which makes this implementation educational rather than production-ready. A production merge sort uses index pointers instead. For a full breakdown including complexity analysis, see the deeper tour.

Quicksort's worst case occurs when the pivot is always the largest or smallest element, which degrades the recursion tree to O(n squared) depth. Choosing the pivot with randrange makes that worst case statistically unlikely across all input distributions. After the pivot is removed with pop, two list comprehensions divide the remaining elements: lesser collects everything at most the pivot and greater collects everything strictly above it. The final return uses list-spread syntax to concatenate the two recursively sorted halves around the pivot in one readable expression. For a full walkthrough of every line in the file, see the deeper tour.

Heap sort runs in two phases: first it rearranges the input list into a max-heap, then it repeatedly extracts the maximum element from the heap root and places it at the end of the sorted region. The heapify function is the atomic operation both phases share. Given an index and a heap boundary, it computes the left child at index 2i + 1 and the right child at 2i + 2, finds which of the three is largest, and if a child is larger it swaps and recurses downward. The doctest proves the behavior: after one call on [1, 4, 3, 5, 2] at index 0, the root becomes 4 as the largest child; a second call promotes 5. For the full heap_sort driver that calls heapify in two phases, see the deeper tour.

Every algorithm seen so far sorts by comparing elements. Radix sort does not: it distributes integers into buckets based on the value of a single digit, then reads the buckets back in bucket order. One pass handles one digit position. The outer while loop repeats for each position, from the ones place up through the highest digit of the maximum element. Inside, int((i / placement) % RADIX) extracts the current digit for each integer and routes it to bucket 0 through 9. The bucket-drain loop then writes the integers back into the list in digit order, preserving the relative order of elements that share the same digit. After all digit positions are processed, the list is sorted in O(n * k) time where k is the number of digits, which beats O(n log n) comparison sorts for large integer sets with bounded digit counts.