Ask a room of developers who last shipped a hand-written sort and you get silence; ask who was grilled on one in an interview and every hand goes up. Sorting algorithms are the push-ups of programming: rarely performed on the job, but they build the muscle the job needs. Here you write linear and binary search plus four classic sorts, then time them against Python’s own sorted().

“Let me see your code and I won’t usually need your flowcharts; show me your data structures and the code will be obvious.”

Fred Brooks, The Mythical Man-Month

Last Updated: July 2026 | Tested on: Python 3.14.6 | Difficulty: Intermediate | Reading Time: 24 minutes

Here is the everyday version. Say a librarian named Aditi has to find one book on a shelf. If the books are in no particular order, she has no choice but to check them one by one from the left until she hits the right title. That is linear search. But if the shelf is sorted by title, she can open to the middle, see whether her book comes before or after, and throw away half the shelf in a single glance. She keeps halving until one book is left. That is binary search, and the difference between the two on a shelf of a million books is the difference between a million checks and about twenty.

Sorting is the flip side of the same coin: it is the work you do once so that every search afterward can be the fast kind. You will almost never ship your own sort in production because sorted() is faster and battle-tested, but writing these by hand is how you learn to reason about recursion, stability, and cost, which is exactly what an interviewer is probing for. Let’s build them and measure them.

Searching: Linear vs Binary

Linear search is the one you already write without thinking: walk the list from the front and return the position the moment you find a match. It works on any list, sorted or not, and it costs O(n) because in the worst case you touch every element. Binary search is the payoff for keeping data sorted. It looks at the middle, decides whether the target is to the left or the right, and discards the other half every step, which is O(log n). The catch that trips everyone up is the boundary bookkeeping, so we will write the clean version first, then deliberately break it.

📄 search.py: linear search and a correct iterative binary search

def linear_search(items, target):
    for i, x in enumerate(items):     # walk from the front
        if x == target:
            return i                  # found it, hand back the position
    return -1                         # fell off the end, not here

def binary_search(items, target):
    lo, hi = 0, len(items) - 1        # inclusive bounds: both ends are fair game
    while lo <= hi:                   # stop only when the window is empty
        mid = (lo + hi) // 2          # middle index, integer division
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1              # target is to the right
        else:
            hi = mid - 1              # target is to the left
    return -1

prices = [12, 19, 23, 41, 55, 68, 77, 90]   # must be sorted for binary search
print("linear_search(prices, 68) ->", linear_search(prices, 68))
print("binary_search(prices, 68) ->", binary_search(prices, 68))
print("binary_search(prices, 50) ->", binary_search(prices, 50))
print("binary_search(prices, 12) ->", binary_search(prices, 12))   # first element
print("binary_search(prices, 90) ->", binary_search(prices, 90))   # last element

▶ Output

linear_search(prices, 68) -> 5
binary_search(prices, 68) -> 5
binary_search(prices, 50) -> -1
binary_search(prices, 12) -> 0
binary_search(prices, 90) -> 7

What happened here: Both searches agree that 68 sits at index 5, but they got there differently. Linear search checked indices 0 through 5 in order. Binary search looked at the middle, compared, and halved: for a list of eight items it needs at most three comparisons instead of up to eight. The value 50 is not in the list, so both return -1, our chosen “not found” signal. The two edge cases matter most: 12 is the very first element and 90 is the very last, and a correct binary search must find both without stepping outside the list. Those two are exactly where a wrong boundary blows up, which is the next demo.

The single most common binary-search bug is the off-by-one in the bounds. If you set the top bound to len(items) instead of len(items) - 1, you have made it point one past the last real index, and the loop can read a slot that does not exist. It often works by accident on small inputs, which is what makes it dangerous. Here it is, failing honestly.

📄 offbyone.py: the classic bad upper bound

# The classic off-by-one: hi = len(items) makes the top bound EXCLUSIVE,
# so the loop can compute a mid that points one past the last real index.
def binary_search_buggy(items, target):
    lo, hi = 0, len(items)            # BUG: hi should be len - 1 for inclusive bounds
    while lo <= hi:                   # BUG: with an exclusive hi this reads past the end
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = [1, 3, 5, 7, 9]
try:
    # search for a value larger than everything: lo marches past the last index
    print(binary_search_buggy(data, 11))
except IndexError as e:
    print("IndexError:", e)

▶ Output

IndexError: list index out of range

What happened here: Searching for 11, a value bigger than every element, keeps pushing lo to the right until it walks off the end, and because hi started one slot too high, the loop is still willing to compute a mid that indexes past the list. Python catches it with an IndexError, but only because we happened to search for an out-of-range value. Search for something in the middle and this same buggy function returns the right answer, which is how the bug survives testing and reaches production.

The fix is to pick one convention and hold it: inclusive bounds mean hi = len - 1 and while lo <= hi, and that pairing is the one in the correct version above.

The 4 Sorting Algorithms You Write in Interviews

Four sorting algorithms cover almost everything you will be asked to write by hand. Bubble sort is the one everybody learns and nobody should ship: it repeatedly swaps neighbors until the list is ordered, at O(n squared). Insertion sort is the honest small-data workhorse, the way you naturally sort a hand of playing cards. Merge sort is the divide-and-conquer classic at a guaranteed O(n log n). Quicksort is its partition-based sibling, usually the fastest of the hand-written bunch. Here are all four, each returning a new sorted list, plus a check that every one agrees with the built-in.

📄 sorts.py: bubble, insertion, merge, and quicksort from scratch

def bubble_sort(items):
    a = items[:]                      # copy so we do not mutate the caller's list
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):    # the biggest value "bubbles" to the end each pass
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:               # already sorted, quit early
            break
    return a

def insertion_sort(items):
    a = items[:]
    for i in range(1, len(a)):
        key = a[i]                    # the card in your hand
        j = i - 1
        while j >= 0 and a[j] > key:  # slide bigger cards to the right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                # drop the card into its slot
    return a

def merge_sort(items):
    if len(items) <= 1:               # a list of 0 or 1 is already sorted
        return items[:]
    mid = len(items) // 2
    left = merge_sort(items[:mid])    # sort the left half
    right = merge_sort(items[mid:])   # sort the right half
    return merge(left, right)         # weave the two sorted halves together

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # <= keeps equal items in original order (stable)
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])              # whatever is left over is already sorted
    out.extend(right[j:])
    return out

def quicksort(items):
    if len(items) <= 1:
        return items[:]
    pivot = items[len(items) // 2]    # pick a middle-ish pivot
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort(less) + equal + quicksort(greater)

if __name__ == "__main__":
  sample = [5, 2, 9, 1, 5, 6, 3, 8, 3, 7]
  print("input:    ", sample)
  print("bubble:   ", bubble_sort(sample))
  print("insertion:", insertion_sort(sample))
  print("merge:    ", merge_sort(sample))
  print("quicksort:", quicksort(sample))
  print("built-in: ", sorted(sample))
  assert bubble_sort(sample) == insertion_sort(sample) == merge_sort(sample) \
         == quicksort(sample) == sorted(sample)
  print("all five agree:", True)

▶ Output

input:     [5, 2, 9, 1, 5, 6, 3, 8, 3, 7]
bubble:    [1, 2, 3, 3, 5, 5, 6, 7, 8, 9]
insertion: [1, 2, 3, 3, 5, 5, 6, 7, 8, 9]
merge:     [1, 2, 3, 3, 5, 5, 6, 7, 8, 9]
quicksort: [1, 2, 3, 3, 5, 5, 6, 7, 8, 9]
built-in:  [1, 2, 3, 3, 5, 5, 6, 7, 8, 9]
all five agree: True

What happened here: All five produce the identical sorted list, and the assert line proves it rather than asking you to eyeball ten numbers. Notice the duplicate values (two 3s, two 5s) all survive, which matters for the stability discussion later. The interesting differences are hidden in how they got there. Bubble and insertion each crawl through the data with nested passes. Merge sort splits the list until every piece is a single element, then merges the pieces back together in order.

Quicksort partitions around a pivot and recurses on the smaller and larger groups. The merge helper is worth staring at: it walks two already-sorted lists with two pointers and always takes the smaller front item, which is the same two-pointer move that powers the “merge two sorted lists” interview question at the end of this post.

Merge sort is the one people find hardest to picture, because the real work happens on the way back up the recursion. The diagram below traces it on [5, 2, 9, 1, 6, 3]. Read top to bottom to watch each list split in half until only single items remain (a single item is sorted by definition), then read the merge lines to watch the sorted pieces get woven back together, pair by pair, until the whole list is ordered.

Tip: click the diagram to open it full screen, then use the zoom and pan controls for a closer look.

The purple root is the original call, the blue nodes are lists still being split, and the green leaves are single items that cannot be split further. Every level of the tree is one halving, which is why the tree is about log n levels deep, and each level does O(n) work to merge, giving merge sort its O(n log n) total. That shape is the reason it never degrades to quadratic the way a careless quicksort can.

The Timing Shootout vs Timsort

Now the honest part. You wrote four sorting algorithms, but Python already ships one called Timsort behind sorted() and list.sort(), and it is written in C with decades of tuning. Let’s put your Python implementations next to it on random lists of growing size and read the clock. The sorted column imports from the sorts.py file above.

📄 shootout.py: your four sorts vs the built-in Timsort

import timeit, random
from sorts import bubble_sort, insertion_sort, merge_sort, quicksort

def bench(func, data, number):
    return timeit.timeit(lambda: func(data), number=number) / number

print(f"{'n':>7} | {'bubble':>11} | {'insertion':>11} | {'merge':>10} | {'quick':>10} | {'sorted()':>10}")
print("-" * 72)
for n in [200, 1_000, 5_000]:
    data = [random.randint(0, 10_000) for _ in range(n)]
    reps = 5
    tb = bench(bubble_sort, data, reps) * 1e3
    ti = bench(insertion_sort, data, reps) * 1e3
    tm = bench(merge_sort, data, reps) * 1e3
    tq = bench(quicksort, data, reps) * 1e3
    ts = bench(sorted, data, 200) * 1e3
    print(f"{n:>7,} | {tb:>9.2f}ms | {ti:>9.2f}ms | {tm:>8.2f}ms | {tq:>8.2f}ms | {ts:>8.4f}ms")

▶ Output

      n |      bubble |   insertion |      merge |      quick |   sorted()
------------------------------------------------------------------------
    200 |      1.77ms |      0.74ms |     0.40ms |     0.24ms |   0.0084ms
  1,000 |     43.28ms |     19.32ms |     1.95ms |     1.47ms |   0.0825ms
  5,000 |   1265.31ms |    500.24ms |    11.75ms |     8.80ms |   0.5467ms

What happened here: Two stories jump out of the table. First, the quadratic sorts fall apart as the input grows. Bubble sort goes from under 2ms at 200 items to over 1,200ms at 5,000, roughly 25 times more items causing hundreds of times more work, the O(n squared) fingerprint you saw in the Big O post. Merge and quicksort stay tame because they are O(n log n): at 5,000 items they finish in about 10ms while bubble sort needs more than a full second.

Second, and more important, look at the sorted() column. At every size it beats your best hand-written sort by a factor of roughly twenty to a hundred, because it runs compiled C rather than interpreted Python and uses tricks like detecting already-sorted runs. That is the whole lesson: write these by hand to understand them and to pass interviews, and call sorted() in every real program you ever ship.

Sorting Real Data: key, Stability, Multi-Key

Real data is rarely a bare list of numbers, and this is where sorting algorithms meet the actual job: dictionaries, tuples, and objects that you want ordered by one of their fields. That is what the key= argument is for: you hand sorted() a function that pulls out the value to compare, and it does the rest. operator.itemgetter is a clean, fast way to build that function for dictionary keys or tuple positions. The other property that matters is stability: Python’s sort never reorders items that compare equal, so their original order is preserved, and you can lean on that to build multi-key sorts by sorting more than once.

📄 keysort.py: key=, itemgetter, stability, and multi-key sorting

from operator import itemgetter

orders = [
    {"name": "Aditi",  "veg": "paneer",   "qty": 2, "total": 240},
    {"name": "Anvay",  "veg": "tofu",     "qty": 5, "total": 240},
    {"name": "Aviraj", "veg": "mushroom", "qty": 1, "total": 90},
    {"name": "Anvi",   "veg": "paneer",   "qty": 3, "total": 360},
]

# sort by a single field with key=
by_total = sorted(orders, key=itemgetter("total"))
print("cheapest first:", [(o["name"], o["total"]) for o in by_total])

# multi-key sort: total DESC, then name A-Z among ties
# trick: sort by name first (secondary), then by total reversed (primary), because
# Python's sort is STABLE so the earlier order survives inside equal keys
step1 = sorted(orders, key=itemgetter("name"))
step2 = sorted(step1, key=itemgetter("total"), reverse=True)
print("total desc, name asc:", [(o["name"], o["total"]) for o in step2])

# proving stability directly: two orders both total 240 keep their input order
same_total = [o["name"] for o in by_total if o["total"] == 240]
print("stable order of the 240 ties:", same_total)

▶ Output

cheapest first: [('Aviraj', 90), ('Aditi', 240), ('Anvay', 240), ('Anvi', 360)]
total desc, name asc: [('Anvi', 360), ('Aditi', 240), ('Anvay', 240), ('Aviraj', 90)]
stable order of the 240 ties: ['Aditi', 'Anvay']

What happened here: The first sort ordered the four orders by total, cheapest first, using itemgetter("total") to pull the number to compare. The multi-key result is the useful trick: to sort by total descending and break ties by name ascending, you sort by the tie-breaker first (name) and then by the primary key (total, reversed). Because the sort is stable, the name ordering set up in step one survives inside each group of equal totals in step two.

You can see it in the last line: Aditi and Anvay both spent 240, and they stay in the order the earlier sort left them, which is proof the sort did not shuffle equal items. This “sort by least significant key first” pattern scales to any number of keys without ever writing a comparison function by hand.

bisect: Searching Sorted Data the Fast Way

Once a list is sorted, the standard-library bisect module gives you binary search without writing the boundary logic yourself, which means you never have to relive the off-by-one bug from the first section. bisect_left finds where a value would go to keep the list ordered, insort inserts while keeping it sorted, and the same tool doubles as a fast range-bucketing device, for example turning a numeric score into a letter grade. Think of it as a phone book that always knows which page your name belongs on.

📄 bisectdemo.py: containment, insertion, and grade bucketing

import bisect

scores = [55, 62, 68, 74, 74, 81, 90, 95]   # kept sorted

# where would 78 go without breaking order?
print("insert point for 78:", bisect.bisect_left(scores, 78))

# fast membership test on a sorted list: O(log n) instead of O(n)
def contains(sorted_items, target):
    i = bisect.bisect_left(sorted_items, target)
    return i < len(sorted_items) and sorted_items[i] == target

print("contains 74:", contains(scores, 74))
print("contains 77:", contains(scores, 77))

# insort keeps a list sorted as you add to it
bisect.insort(scores, 78)
print("after insort 78:", scores)

# turn a numeric score into a letter grade with bisect: the classic use
breakpoints = [60, 70, 80, 90]        # boundaries between grades
grades = "FDCBA"                      # 5 buckets for 4 boundaries
for s in [55, 68, 74, 81, 95]:
    letter = grades[bisect.bisect_right(breakpoints, s)]
    print(f"score {s} -> grade {letter}")

▶ Output

insert point for 78: 5
contains 74: True
contains 77: False
after insort 78: [55, 62, 68, 74, 74, 78, 81, 90, 95]
score 55 -> grade F
score 68 -> grade D
score 74 -> grade C
score 81 -> grade B
score 95 -> grade A

What happened here: bisect_left reported that 78 belongs at index 5, right after the two 74s and before 81, without you doing any comparisons yourself. The contains helper wraps that into an O(log n) membership test: it finds the insert point and checks whether the item actually sitting there equals the target, which is why 74 is found and 77 is not. insort then dropped 78 into that exact slot, keeping the list sorted in one call.

The grade example is the pattern worth remembering: given sorted boundaries, bisect_right tells you which bucket a value falls into, so a score of 74 lands in bucket 2 and indexes into "FDCBA" to give a C. That is a clean, branch-free replacement for a long chain of if score >= 90 ... elif conditions.

Common Mistakes

❌ Mistake: Running binary search on unsorted data

# Bad: the list is not sorted, so "go left or right" is meaningless
nums = [8, 3, 5, 1, 9, 2]
# binary_search(nums, 9)  -> may return -1 even though 9 is present

# Good: sort first (once), then every search after is a fast binary search
nums.sort()                 # [1, 2, 3, 5, 8, 9]
# now binary_search(nums, 9) is correct and O(log n)

Why: Binary search only works because “the target is smaller, so look left” is a reliable statement, and that is only true when the data is sorted. Point it at an unsorted list and it will confidently discard the half that actually holds your value, returning “not found” for an item that is right there. If you are going to search a collection many times, sort it once up front and reuse the order; if you search it only once, a plain linear scan is simpler and avoids the sort cost entirely.

❌ Mistake: Shipping your own sort instead of the built-in

# Bad: a hand-written sort in production code
result = quicksort(records)          # slower, unstable, and one more thing to test

# Good: the built-ins are faster, stable, and already tested
result = sorted(records, key=itemgetter("date"))   # returns a new sorted list
records.sort(key=itemgetter("date"))               # sorts in place

Why: The shootout showed sorted() beating every hand-written sort by a wide margin, and it is also stable and thoroughly tested, three things your own quicksort is not. The naive quicksort above also has a worst case of O(n squared) on already-sorted or all-equal input, exactly the kind of data that shows up in the wild. Write these algorithms to learn and to interview, then delete them and call the standard library in anything that ships.

Best Practices

• Reach for sorted() and list.sort() first. They are C-fast, stable, and correct. Hand-written sorting algorithms are for learning and interviews, not production.
• Sort once, search many with bisect. If you look things up repeatedly in a collection that does not change often, keep it sorted and use bisect for O(log n) lookups instead of O(n) scans.
• Pick one binary-search convention. Inclusive bounds (hi = len - 1, while lo <= hi) or half-open (hi = len, while lo < hi), but never mix them. Mixing is where the off-by-one lives.
• Use key= and multi-pass stable sorts instead of writing comparison functions. Sort by the least significant key first, then the most significant, and let stability do the rest.
• Know the cost class of what you write. A nested-loop sort is O(n squared) and will time out at scale; merge and quicksort are O(n log n). State the complexity out loud in interviews before you are asked.

Wrapping Up

You built the core of the algorithms toolkit from nothing: linear and binary search, four sorting algorithms, and the standard-library bisect that packages binary search so you never have to fight the boundaries again. The measurements told the real story. The O(n squared) sorts crumbled as the data grew while the O(n log n) sorts stayed calm, and Python’s own sorted() beat every one of your hand-written versions by a wide margin because it runs compiled and tuned code.

That is the balance to carry forward: understand these sorting algorithms deeply because interviews test them and because they teach recursion, stability, and cost, but reach for the built-in tools in everything you actually ship. All of this is evergreen and stdlib-only, so it works the same in Python 3.14.6 today as it will years from now.

Next in this chapter we build the data structures these algorithms run on, starting with stacks, queues, and linked lists and the collections.deque that makes them fast. you can pick your next topic from the Python + AI/ML tutorial series home.

Frequently Asked Questions

Try It Yourself: Interview Variations

These five are the classic variations built on the search and merge patterns above, and they show up constantly in coding rounds. Read each one, try it on paper first, then check against the run below. Every function here is a small twist on binary search or the two-pointer merge you already wrote.

📄 drills.py: rotated search, first/last occurrence, merge, and peak

# 1. Search a rotated sorted array in O(log n): [4,5,6,7,0,1,2]
def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:          # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                              # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

# 2 & 3. First and last index of a target in a sorted list with duplicates
def first_occurrence(nums, target):
    lo, hi, ans = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            ans = mid; hi = mid - 1        # keep going LEFT for the first one
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

def last_occurrence(nums, target):
    lo, hi, ans = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            ans = mid; lo = mid + 1        # keep going RIGHT for the last one
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

# 4. Merge two sorted lists into one sorted list in O(n + m)
def merge_two(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:]); out.extend(b[j:])
    return out

# 5. Peak element: index whose value is >= both neighbors, in O(log n)
def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                   # climb toward the higher side
        else:
            hi = mid
    return lo

print("search_rotated([4,5,6,7,0,1,2], 0) ->", search_rotated([4,5,6,7,0,1,2], 0))
print("search_rotated([4,5,6,7,0,1,2], 3) ->", search_rotated([4,5,6,7,0,1,2], 3))
dupes = [2, 4, 4, 4, 7, 9, 9]
print("first_occurrence(dupes, 4) ->", first_occurrence(dupes, 4))
print("last_occurrence(dupes, 4)  ->", last_occurrence(dupes, 4))
print("merge_two([1,4,7],[2,3,8,10]) ->", merge_two([1,4,7],[2,3,8,10]))
print("find_peak([1,3,7,4,2]) ->", find_peak([1,3,7,4,2]))

▶ Output

search_rotated([4,5,6,7,0,1,2], 0) -> 4
search_rotated([4,5,6,7,0,1,2], 3) -> -1
first_occurrence(dupes, 4) -> 1
last_occurrence(dupes, 4)  -> 3
merge_two([1,4,7],[2,3,8,10]) -> [1, 2, 3, 4, 7, 8, 10]
find_peak([1,3,7,4,2]) -> 2

What happened here: Each of these is binary search with one extra idea bolted on. search_rotated works out which half is sorted at every step and searches that half, still in O(log n) despite the rotation. first_occurrence and last_occurrence do not stop at the first match; they record it and keep searching left or right to pin down the very first or very last position among duplicates, which is why they return 1 and 3 for the block of 4s. merge_two is the exact two-pointer merge from merge sort, reused on its own.

find_peak shows that binary search does not even need sorted data, only a rule that reliably tells it which direction to go: here it always climbs toward the higher neighbor and lands on a peak. Master these five and you have covered a large slice of the search questions asked in real interviews.

Interview Questions on Sorting and Searching

These come from real screens and onsites. Practice answering before you read each answer.

Q: Implement binary search and tell me its time and space complexity.

The iterative version keeps two bounds, checks the middle element, and discards half the range each step, which is O(log n) time and O(1) space because it reuses a couple of index variables. The recursive version is also O(log n) time but O(log n) space due to the call stack. The one thing to say out loud is that the input must be sorted, and that you are using inclusive bounds with a while lo <= hi loop to avoid the off-by-one.

Q: Why is Python’s built-in sort faster than a quicksort you write yourself?

Because sorted() runs Timsort implemented in C, while your quicksort runs as interpreted Python, and that alone is a large constant-factor gap. Timsort also detects already-sorted runs and merges them cheaply, so it approaches O(n) on partially ordered data, and it is stable. My hand-written quicksort is pure Python, can degrade to O(n squared) on bad pivots, and is not stable. Same big-O class for the average case, very different real-world speed.

Q: What makes a sort stable, and give a case where stability changes the answer.

A stable sort preserves the original order of items that compare equal. It matters whenever you sort by multiple keys in stages. If you first sort a list of orders by name and then by total, a stable sort keeps the name order intact within each group of equal totals, so you get “total ascending, name ascending” for free. An unstable sort would scramble the names inside each total group and the multi-key result would be wrong.

Q: How do you find the first occurrence of a value in a sorted list with duplicates?

Run a binary search, but when you hit the target do not return immediately. Record the index and keep searching the left half by setting hi = mid - 1, because an earlier occurrence might still be to the left. When the loop ends, the last recorded index is the first occurrence. It stays O(log n), and swapping “search left” for “search right” gives you the last occurrence instead. The bisect module’s bisect_left does the same job in one call.

Q: When would you choose insertion sort over merge sort?

On very small inputs or on data that is already nearly sorted. Insertion sort is O(n squared) in general but O(n) on almost-sorted data and has tiny constant factors and no recursion overhead, so it wins on short lists. This is not just trivia: Timsort itself falls back to insertion sort for small runs before merging them, which is part of why the built-in is so fast on real data.

Q: You need to repeatedly check membership and also insert while keeping order. What do you use?

If order does not matter for the membership test, a set gives O(1) lookups and is the simplest answer. If you specifically need the collection kept in sorted order (for range queries or ordered iteration), keep a list sorted and use the bisect module: bisect_left for O(log n) containment and insort to add in the right place. Reaching for bisect here signals that you know binary search without re-deriving the boundaries.

Go deeper: when you outgrow this post, the official Python documentation is the next stop.

Related Posts

Previous: Python Time Complexity: Lists, Dicts, Sets Under the Hood

Next: Stacks and Queues in Python, Explained With deque

Series Home: Python + AI/ML Tutorial Series