Which Sort When?

The Idea

Ask three questions: how big is the input, what do you already know about it, and does stability matter. Small or nearly sorted favours insertion sort, and small integer ranges favour counting sort. Everything else goes to quick or merge sort.

Real-World Example

A photo app arranging 40 shots by date can use anything at all. The same app organising a 200,000-image library needs an O(n log n) sort, and a stable one, so photos taken in the same second keep their capture order.

The Code

def choose_sort(n, nearly_sorted, small_int_range, needs_stable):
    if n <= 32 or nearly_sorted:
        return "insertion sort"       # tiny overhead wins
    if small_int_range:
        return "counting sort"        # O(n + k), no comparisons
    if needs_stable:
        return "merge sort"           # stable, guaranteed n log n
    return "quick sort"               # fast in place, average n log n

print(choose_sort(1000, False, False, True))   # merge sort