Sorting Algorithms and Their Trade-offs

What sorting gives you

Sorting puts values into a chosen order. Once data is ordered, adjacent duplicates are easy to spot, two-pointer scans become possible, and binary search can answer membership queries in O(log n).

The comparison model has a useful limit: a general comparison sort cannot guarantee better than O(n log n). Specialised methods such as counting sort can be faster only when keys have extra structure, such as integers in a small known range.

Three useful ideas

Insertion sort grows a sorted prefix. It is O(n²) in the worst case, but it is simple, stable and fast for tiny or nearly sorted inputs.

Merge sort splits the array, sorts both halves, and merges them. It guarantees O(n log n) time and is stable, but ordinary array implementations need O(n) extra space.

Quicksort partitions values around a pivot, then sorts the two sides. It is usually fast and can work in place, but poor pivot choices can produce O(n²) time. Randomised pivots make that bad case unlikely.

Properties that matter

A sort is stable if equal keys keep their original relative order. If students are sorted by score after already being sorted by name, a stable score sort preserves name order among equal scores.

Stable merge sort

The implementation below sorts records by score. During a tie, it takes the left record first; that one choice preserves the original order of equal scores.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i][1] <= right[j][1]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]


records = [("Asha", 82), ("Kabir", 75), ("Meera", 82), ("Rohan", 68)]
result = merge_sort(records)
print("order:", ", ".join(name for name, _ in result))
print("scores:", " ".join(str(score) for _, score in result))

order: Rohan, Kabir, Asha, Meera
scores: 68 75 82 82

How to choose

Ask what the input promises. Nearly sorted and small can favour insertion sort. Guaranteed worst-case performance and stability point toward merge sort. Tight memory and strong average performance may favour quicksort. Integer keys in a narrow range may allow counting sort. Also ask whether a full sort is necessary: a heap can find the smallest few items, and selection algorithms can find one rank without ordering everything.