Skip to content
Tutorials Center
My learning

Topics

Lesson 143 of 149 ยท Data Structures and Algorithms

Searching and Sorting Algorithms

Learn classic Python algorithms, including linear and binary search, bisect, bubble, insertion, merge and quick sort, and measuring Big-O by timing your code.

An algorithm is a precise recipe for solving a problem. Searching and sorting are the two problems every programmer meets first, and they're perfect for learning how to think about efficiency: there are several correct solutions, and on large inputs some of them are thousands of times faster than others.

In this lesson you'll write linear and binary search, use the standard library's bisect module, implement four classic sorting algorithms, and then measure them so Big-O stops being abstract. In real projects you'll almost always call sorted() and bisect, but knowing what happens underneath helps you pick the right tool, spot slow code, and answer the interview questions that love this topic. The data structures lesson introduced the notation; here you'll see it in action.

Big-O in one page

Big-O notation describes how the work an algorithm does grows as the input size n grows. It ignores constant factors and focuses on the shape of the growth:

Big-O Name If n doubles, the work... Example
O(1) constant stays the same items[i], dict lookup
O(log n) logarithmic grows by one step binary search
O(n) linear doubles linear search, sum()
O(n log n) linearithmic a bit more than doubles merge sort, sorted()
O(nยฒ) quadratic quadruples bubble sort, nested loops over the same data

Usually you care about the worst case, sometimes the average case. An O(nยฒ) algorithm can be perfectly fine for 50 items and unusable for 5 million.

The simplest search checks every item in turn until it finds a match. It works on any list, sorted or not, and takes O(n) time in the worst case:

Python Linear search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The in operator and list.index() are linear searches too, just written in C. If you search the same large collection over and over, convert it to a set or dictionary once and enjoy O(1) lookups.

If the data is sorted, you can do much better. Look at the middle item. If it's too small, the target can only be in the right half; if it's too big, only in the left half. Each step throws away half of what's left, so a million items take at most about 20 steps. That's O(log n):

Python Binary search, step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Even with 143 numbers, each search needs only a handful of checks. Binary search is famous for off-by-one bugs, so pay attention to the details: low <= high (not <), and moving past middle with + 1 and - 1 so the range always shrinks.

The bisect module

You rarely need to write binary search yourself. The bisect module finds positions in a sorted list in O(log n):

  • bisect_left(items, x) returns the first position where x could be inserted while keeping the order. If x is present, that's its index.
  • bisect_right(items, x) (also called bisect) returns the position after any existing copies of x.
  • insort(items, x) inserts x in the right place.
Python Using bisect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The grading trick is a neat bisect pattern: the position of a value among sorted boundaries tells you which bucket it falls into. Since Python 3.10, the bisect functions also accept a key= function, so you can search a sorted list of records by one field.

Note: insort() finds the position in O(log n), but inserting into a list still shifts the later items, which is O(n). It's great for keeping a moderately sized list sorted, not for millions of inserts.

Sorting algorithms

Python's built-in sorted() and list.sort() are excellent and you should use them in real code. Writing a few sorting algorithms yourself, though, is the classic way to see why some approaches scale and others don't. Each function below returns a new sorted list and leaves its input alone.

Bubble sort: O(nยฒ)

Bubble sort walks through the list comparing neighbors and swapping them when they're in the wrong order. After each pass, the largest remaining value has "bubbled" to the end. It stops early when a pass makes no swaps:

Python Bubble sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It's easy to understand and almost never used in practice: for n items it makes up to about nยฒ/2 comparisons.

Insertion sort: O(nยฒ), but fast on nearly sorted data

Insertion sort builds a sorted section at the front, one item at a time, the way many people sort playing cards in their hand. Each new item slides left until it reaches its place:

Python Insertion sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The worst case is still O(nยฒ), but on data that's already almost sorted, each item moves only a little, so it runs in close to O(n). That's why real-world sorting algorithms use insertion sort for small pieces.

Merge sort: O(n log n)

Merge sort is a divide-and-conquer algorithm: split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. Splitting creates about log n levels, and merging each level touches all n items, giving O(n log n) in every case:

Python Merge sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merge sort is stable: items that compare equal keep their original order. The price is extra memory for the merged lists.

Quick sort: O(n log n) on average

Quick sort picks a pivot, splits the other values into "smaller", "equal" and "larger" groups, and sorts the outer groups recursively. With list comprehensions it fits in a few lines:

Python Quick sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On average each split divides the data roughly in half, giving O(n log n). If the pivot is always the smallest or largest value, the splits are lopsided and it degrades to O(nยฒ). Choosing a random pivot makes that worst case extremely unlikely. Production versions sort in place to save memory, but the idea is the same.

Timing the algorithms

Big-O predicts the trend; a stopwatch shows it. Let's time each sort on random data of growing size with time.perf_counter(). Watch how bubble sort's time roughly quadruples when n doubles, while merge sort's only a little more than doubles:

Python Race the sorts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Your exact numbers will vary from run to run, but the pattern doesn't: bubble sort falls further behind with every doubling, and the built-in sorted() beats them all. For more precise measurements, use the timeit module from the performance lesson.

What Python actually uses

sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort designed for real-world data, which often contains already-sorted runs. It's O(n log n) in the worst case, close to O(n) on nearly sorted input, and stable. It's implemented in C, so it beats any pure-Python sort by a wide margin.

Stability is what makes multi-level sorting easy: sort by the secondary key first, then by the primary key, and ties keep the earlier order. Usually a key= tuple is simpler still:

Python Sorting records like a pro

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing an approach

Situation Best tool Cost
Search an unsorted list once in / list.index() O(n)
Search the same data many times build a set or dict first O(1) per lookup
Search or insert in sorted data bisect O(log n) to find
Sort anything sorted() / list.sort() with key= O(n log n)
Only need the top or bottom k heapq.nlargest() / nsmallest() O(n log k)
Learn or explain the ideas bubble, insertion, merge, quick sort O(nยฒ) to O(n log n)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What must be true before you can use binary search?

    Binary search decides which half to discard by comparing with the middle item, which only works on sorted data.
  2. 2. About how many steps does binary search need for one million sorted items?

    Each step halves the range, and 2 to the power of 20 is about one million, so it's O(log n).
  3. 3. An algorithm is O(nยฒ). Roughly what happens to its running time when the input doubles?

    (2n)ยฒ = 4nยฒ, so doubling the input multiplies the work by about four.
  4. 4. With scores = [10, 20, 20, 30], what does bisect_right(scores, 20) return?

    bisect_right returns the position after the existing 20s, which is index 3.
  5. 5. What does it mean that Python's sort is stable?

    Stability lets you sort by one key and keep an earlier ordering for ties.

Summary

  • Big-O describes growth: O(1), O(log n), O(n), O(n log n) and O(nยฒ) are the classes you'll meet most.
  • Linear search works on any list in O(n); in and index() use it. Build a set or dict for repeated lookups.
  • Binary search needs sorted data and runs in O(log n); the bisect module gives you bisect_left, bisect_right and insort.
  • Bubble and insertion sort are O(nยฒ); insertion sort is quick on nearly sorted data.
  • Merge sort is O(n log n) and stable; quick sort averages O(n log n) and uses a random pivot to avoid its worst case.
  • Time code with time.perf_counter() or timeit to confirm what Big-O predicts.
  • In real code, use sorted() / list.sort() (Timsort, stable) with key=.

Next: Python Cheat Sheet, a one-page review of the syntax and tools you've learned in this course.