Searching and Sorting

Linear search

The simplest way to find something is to look at every item in turn until you find it or run out of items. This is linear search (or sequential search).

FUNCTION linear_search(list, target)
    FOR index FROM 0 TO length of list − 1
        IF list[index] = target THEN
            RETURN index
        END IF
    END FOR
    RETURN −1                 // not found
END FUNCTION

def linear_search(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1                               # not found


fruit = ["pear", "apple", "kiwi", "plum", "fig"]
print(linear_search(fruit, "plum"))
print(linear_search(fruit, "mango"))

3
-1

Linear search needs no preparation and works on any sequence, in any order. Its weakness is its cost: for n items it makes up to n comparisons — all n when the item is missing. Python's in operator and list.index() do exactly this.

Binary search

If the data is sorted, you can do much better. Binary search compares the target with the middle item. If they are equal, it is done. If the target is larger, it can only be in the right half; if it is smaller, only in the left half. Either way, half of the remaining items are discarded with one comparison — the way you look up a word in a paper dictionary.

The search keeps two positions, low and high, that mark the part of the list where the target can still be. The loop ends when the target is found or when low passes high: the range is empty and the target is not there. To compare the two methods, this version of each also counts its comparisons:

def linear_search(items, target):
    steps = 0
    for index, item in enumerate(items):
        steps += 1
        if item == target:
            return index, steps
    return -1, steps


def binary_search(items, target):
    low, high = 0, len(items) - 1
    steps = 0
    while low <= high:
        steps += 1
        middle = (low + high) // 2
        if items[middle] == target:
            return middle, steps
        if items[middle] < target:
            low = middle + 1                # target is in the right half
        else:
            high = middle - 1               # target is in the left half
    return -1, steps


numbers = list(range(0, 2_000_000, 2))      # 0, 2, 4, …: sorted
print(f"{len(numbers):,} sorted numbers")
for target in [0, 1_000_000, 1_999_998, 7]:
    _, linear_steps = linear_search(numbers, target)
    index, binary_steps = binary_search(numbers, target)
    print(f"{target:>9,}  index {index:>7,}  "
          f"linear {linear_steps:>9,}  binary {binary_steps:>2}")

1,000,000 sorted numbers
        0  index       0  linear         1  binary 19
1,000,000  index 500,000  linear   500,001  binary 19
1,999,998  index 999,999  linear 1,000,000  binary 20
        7  index      -1  linear 1,000,000  binary 20

Each step halves the range, so a million items shrink to one after about 20 halvings (2²⁰ = 1,048,576). Doubling the data adds only one step. That is logarithmic growth, O(log n), explained in Algorithmic Complexity. Python's standard module bisect provides a ready-made binary search.

Why sorting matters

A sorting algorithm puts items in order according to a comparison: numbers from small to large, names alphabetically, orders by date. Sorted data is easier for people to read, but it also makes other work fast: binary search needs it, duplicates end up next to each other, and the smallest, largest or median value is found by position.

Sorting is one of the most studied problems in computing, and the classic algorithms below are worth knowing even though you will rarely write one: they show, in a small space, how different strategies lead to very different costs. Each one below sorts the same list, [5, 2, 4, 6, 1, 3], and is checked against Python's built-in sorted() on all 5,040 orderings of seven numbers.

Bubble sort

Bubble sort walks through the list comparing neighbors, and swaps each pair that is in the wrong order. After the first pass the largest item has "bubbled up" to the end; after the second pass the second-largest is in place, and so on. If a pass makes no swaps, the list is sorted and the algorithm can stop early.

from itertools import permutations


def bubble_sort(items):
    items = list(items)                     # sort a copy
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for i in range(end):                # items after `end` are final
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                     # a pass without swaps: sorted
            break
    return items


print(bubble_sort([5, 2, 4, 6, 1, 3]))
tests = list(permutations([3, 1, 4, 1, 5, 9, 2]))
print(all(bubble_sort(t) == sorted(t) for t in tests), len(tests))

[1, 2, 3, 4, 5, 6]
True 5040

Bubble sort is easy to understand and sorts in place, but it is slow: for n items it makes about n²/2 comparisons, O(n²). Its only strength is that an already sorted list takes a single pass. It is taught, not used.

Insertion sort

Insertion sort works the way many people sort a hand of cards. The left part of the list is kept sorted. Each step takes the next item and moves it left, past every larger item, until it reaches its place in the sorted part.

from itertools import permutations


def insertion_sort(items):
    items = list(items)
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:  # shift larger items right
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current                # drop it into the gap
    return items


print(insertion_sort([5, 2, 4, 6, 1, 3]))
tests = list(permutations([3, 1, 4, 1, 5, 9, 2]))
print(all(insertion_sort(t) == sorted(t) for t in tests), len(tests))

[1, 2, 3, 4, 5, 6]
True 5040

Insertion sort is also O(n²) in general, but it is fast on small or nearly sorted lists: when every item is already close to its place, the inner loop barely runs, and a sorted list costs only O(n). That is why real-world sorts, including Python's, use insertion sort for short runs of data.

Merge sort

Merge sort is a divide-and-conquer algorithm (see Recursion). It splits the list in half, sorts each half recursively, and then merges the two sorted halves: it repeatedly takes the smaller of the two front items, which produces one sorted list in a single pass. A list of one item is already sorted — the base case.

split   [5, 2, 4, 6, 1, 3]
split   [5, 2, 4]            [6, 1, 3]
split   [5]  [2, 4]          [6]  [1, 3]
split        [2] [4]              [1] [3]
merge   [5]  [2, 4]          [6]  [1, 3]
merge   [2, 4, 5]            [1, 3, 6]
merge   [1, 2, 3, 4, 5, 6]

from itertools import permutations


def merge_sort(items):
    if len(items) <= 1:                      # base case
        return list(items)
    middle = len(items) // 2
    left = merge_sort(items[:middle])        # divide and conquer
    right = merge_sort(items[middle:])
    return merge(left, right)                # combine


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:              # <= keeps equal items in order
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])                  # one side may have items left
    result.extend(right[j:])
    return result


print(merge_sort([5, 2, 4, 6, 1, 3]))
tests = list(permutations([3, 1, 4, 1, 5, 9, 2]))
print(all(merge_sort(t) == sorted(t) for t in tests), len(tests))

[1, 2, 3, 4, 5, 6]
True 5040

The list can be halved about log₂ n times, and each level of merging handles all n items once, so merge sort takes O(n log n) steps — always, whatever the input order. The price is memory: merging needs a second list of n items.

Quicksort

Quicksort also divides and conquers, but does the work before the recursion instead of after it. It picks one item as the pivot and partitions the list: items smaller than the pivot go to one side, larger items to the other. The pivot is now in its final place, and each side is sorted recursively. No merge step is needed.

[5, 2, 4, 6, 1, 3]   pivot 6 → [5, 2, 4, 1, 3] + [6] + []
[5, 2, 4, 1, 3]      pivot 4 → [2, 1, 3] + [4] + [5]
[2, 1, 3]            pivot 1 → [] + [1] + [2, 3]
[2, 3]               pivot 3 → [2] + [3] + []
result               [1, 2, 3, 4, 5, 6]

from itertools import permutations


def quicksort(items):
    if len(items) <= 1:                          # base case
        return list(items)
    pivot = items[len(items) // 2]               # the middle item
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)


print(quicksort([5, 2, 4, 6, 1, 3]))
tests = list(permutations([3, 1, 4, 1, 5, 9, 2]))
print(all(quicksort(t) == sorted(t) for t in tests), len(tests))

[1, 2, 3, 4, 5, 6]
True 5040

This version shows the idea clearly but builds new lists at every level. Production quicksorts partition in place, by swapping items within the one list, which makes them very fast in practice and frugal with memory.

Quicksort's speed depends on the pivot. When it splits the list into two roughly equal halves, quicksort takes O(n log n) on average. When the pivot is always the smallest or largest item — as happens if you always pick the first item and the list is already sorted — every partition peels off only one item, and the cost degrades to O(n²). Real implementations avoid this by choosing the pivot at random or as the median of several items, and some switch to another algorithm when the recursion gets too deep.

Stable and unstable sorting

When two items compare as equal, a sort may put them in either order. A stable sort guarantees to keep equal items in the order they had before sorting. With plain numbers this makes no visible difference, but with records it does, because records that are "equal" by the sort key can differ in other fields.

Stability lets you sort by several keys: sort by the secondary key first, then by the primary key. Here, students are sorted by grade, and within each grade by name:

students = [("Noor", "B"), ("Sam", "A"), ("Ada", "B"), ("Lee", "A"), ("Mia", "C")]

by_name = sorted(students, key=lambda s: s[0])     # secondary key first
by_grade = sorted(by_name, key=lambda s: s[1])     # then the primary key

for name, grade in by_grade:
    print(grade, name)

A Lee
A Sam
B Ada
B Noor
C Mia

Because Python's sort is stable, the second sort keeps Lee before Sam and Ada before Noor, as the first sort left them. An unstable sort could produce "A Sam" before "A Lee". Bubble sort, insertion sort and merge sort (with <= in the merge) are stable; the usual in-place quicksort is not. In Python you can also sort by both keys at once with a tuple key: sorted(students, key=lambda s: (s[1], s[0])).

Comparing the algorithms

The table summarizes how the running time grows with the number of items n, how much extra memory each algorithm needs, and whether it is stable. Quicksort's figures are for the usual in-place version.

The "best" column for bubble sort and insertion sort applies to input that is already sorted. Quicksort's O(log n) extra space is the depth of its recursion, when it recurses into the smaller side and loops over the larger one.

Sorting in real languages

You will almost never write a sort yourself. Every mainstream language ships one that is faster and better tested than a hand-written version:

• Python: sorted() and list.sort() use Timsort, designed by Tim Peters for Python in 2002: an adaptive merge-sort hybrid that finds runs of already-ordered items, extends short runs with insertion sort, and merges them. Python 3.11 refined the way it decides which runs to merge (a strategy called Powersort). It is stable and very fast on partly sorted data. See Lists and Tuples for how to use it.
• JavaScript: Array.prototype.sort() must be stable since ECMAScript 2019. Note that without a compare function it sorts by the text of the items, so [10, 9, 1].sort() gives [1, 10, 9]; pass (a, b) => a - b to sort numbers.
• Java uses a Timsort for objects and a quicksort variant (dual-pivot quicksort) for primitive types such as int, where stability does not matter.
• C's qsort() does not promise any particular algorithm, no stability, nor any running time.