Skip to main content

Sorting

Various implementations of sorting algorithms.

Tim Sort​

Python's default sorting algorithm.

sorted(iterable)

or

the_list.sort(*, key=None, reverse=False)

Heap Sort​

import heapq

def heap_sort(iterable):
    heapq.heapify(iterable)
    return [heapq.heappop(h) for _ in range(len(h))]

heap_sort(the_list)

Selection Sort​

def selection_sort(self, iterable) -> None:
    for i in range(len(iterable)):
        argmin = min(range(i, len(iterable)), key=lambda x: iterable[x])
        iterable[i], iterable[argmin] = iterable[argmin], iterable[i]

Merge Sort​

def _merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(iterable):
    if len(iterable) <= 1:
        return iterable
    middle = len(iterable) // 2
    left = merge_sort(iterable[:middle])
    right = merge_sort(iterable[middle:])
    return _merge(left, right)

Quick Sort​

def quick_sort(iterable):
    if len(iterable) <= 1:
        return iterable
    pivot = iterable[len(iterable) // 2]
    left = [x for x in iterable if x < pivot]
    middle = [x for x in iterable if x == pivot]
    right = [x for x in iterable if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Reference​