I1 · Python Programming for AI

Sorting Algorithms

A sorting algorithm puts items in order. Selection sort repeatedly finds the smallest remaining item and moves it to the front. Bubble sort repeatedly swaps neighbouring items that are in the wrong order. Insertion sort takes items one at a time and inserts each into its correct place among those already sorted.

12 min Intermediate · Sublevel Beginner Jump to the activity

What you need: The earlier topics of this module.

Definition

How would you arrange a pile of answer sheets by marks, by hand?

A sorting algorithm puts items in order. Selection sort repeatedly finds the smallest remaining item and moves it to the front. Bubble sort repeatedly swaps neighbouring items that are in the wrong order. Insertion sort takes items one at a time and inserts each into its correct place among those already sorted.

In simple words

Selection sort: find the lowest mark, put it first; find the next lowest, put it second. Bubble sort: walk along the line, swapping any neighbours in the wrong order; big numbers 'bubble' to the end. Insertion sort: like sorting playing cards in your hand, slide each new card into place.

Overview

  • Sorting arranges items in order, such as smallest to largest or A to Z.
  • Sorted data makes searching, finding medians, ranking and removing duplicates easier.
  • Simple sorts take about n² steps; efficient sorts take about n log n.
  • A sort is stable if equal items keep their original order, and in-place if it needs little extra memory.
  • Python's sorted() and list.sort() use Timsort, a stable hybrid of merge sort and insertion sort.
  • Learning the classic sorts teaches algorithm design, even though you will usually call sorted().

Why it matters

Sorting comes before binary search, before finding medians, and before ranking search results. Writing simple sorts by hand teaches comparisons, swaps and loops inside loops, and shows why Python's built-in sorted() is so much faster.

Key terms

Sorting
Arranging items in order, such as smallest to largest.
Comparison sort
A sort that orders items by comparing pairs of them.
Swap
Exchanging the positions of two items.
In-place sort
A sort that rearranges the original list without making a new one.
Stable sort
A sort that keeps equal items in their original relative order.
Timsort
The fast, stable algorithm behind Python's sorted() and list.sort().

Types

There are many sorting algorithms. These six are the ones every programmer learns, from the simplest to the one Python actually uses.

1. Bubble sort

Repeatedly swapping neighbouring items that are in the wrong order.

  • How it works: Each pass carries the largest remaining item to the end like a rising bubble; stop when a pass makes no swaps; O(n²), stable, in-place.
  • Example: Sorting [5, 1, 4, 2]: the first pass gives [1, 4, 2, 5].
  • When to use it: Use it only for teaching or tiny lists; it is too slow for real data.

2. Selection sort

Repeatedly finding the smallest remaining item and putting it next in place.

  • How it works: For each position, scan the rest of the list for the minimum and swap it in; always O(n²) comparisons but at most n − 1 swaps; not stable.
  • Example: Arranging students by height by picking the shortest one each time.
  • When to use it: Use it when writing data is expensive, since it makes very few swaps.

3. Insertion sort

Building a sorted part one item at a time by inserting each new item where it belongs.

  • How it works: Take the next item and shift larger sorted items right until its place is found; O(n²) in the worst case but close to O(n) on nearly sorted data; stable.
  • Example: Sorting playing cards in your hand as you pick them up.
  • When to use it: Use it for small or nearly sorted lists; Timsort uses it for short runs.

4. Merge sort

A divide-and-conquer sort that splits the list, sorts each half and merges them.

  • How it works: Split until lists have one item, then merge pairs by repeatedly taking the smaller front item; always O(n log n), stable, needs O(n) extra memory.
  • Example: Merging two sorted marks lists from two sections into one ranked list.
  • When to use it: Use it when you need guaranteed speed and stability, or to sort data too large for memory.

5. Quick sort

A divide-and-conquer sort that picks a pivot and partitions items into smaller and larger groups.

  • How it works: Items less than the pivot go left and greater go right, then each side is sorted recursively; average O(n log n), worst O(n²), in-place, not stable.
  • Example: Choosing 50 as pivot for [72, 15, 50, 91, 33] gives [15, 33] + [50] + [72, 91].
  • When to use it: Use it for fast general sorting in memory; a random pivot avoids the worst case.

6. Timsort (Python's built-in sort)

A hybrid sort designed by Tim Peters in 2002 that combines merge sort and insertion sort.

  • How it works: It finds runs that are already sorted, extends short runs with insertion sort and merges runs cleverly; O(n log n) worst case, O(n) on sorted data, stable.
  • Example: sorted(marks) and students.sort(key=...) both use it.
  • When to use it: Use it in practice: call sorted() or list.sort() instead of writing your own sort.

Explained in detail

Why study sorting at all?

In real programs you will almost always call sorted() or list.sort(). Studying simple sorting algorithms is still worthwhile because they are the clearest examples of how the same task can be done in different ways with very different costs. They also train the skills of tracing, reasoning about loops and spotting off-by-one errors, and they are a staple of technical interviews and exams.

Three simple sorts compared

AlgorithmIdeaGood to know
Selection sortFind the smallest remaining item and swap it to the front; repeatAlways does about n²/2 comparisons, even on sorted data; few swaps
Bubble sortSwap neighbours that are out of order; large items bubble to the endCan stop early if a pass makes no swaps; usually the slowest in practice
Insertion sortTake each item and insert it into place among those already sortedVery fast on nearly sorted data; how people sort a hand of cards

All three take time proportional to n² in the worst case: double the list and the work roughly quadruples. Sorting 10,000 items with them means tens of millions of comparisons.

Faster sorts

Cleverer algorithms reach about n log n. Merge sort, described by John von Neumann in 1945, splits the list in half, sorts each half and merges them. Quicksort, invented by Tony Hoare in 1959, picks a pivot and partitions items around it. Python uses Timsort, designed by Tim Peters in 2002, which combines merge sort and insertion sort and is especially fast on real data that is already partly ordered. It is stable, so if you sort students by name and then by mark, students with equal marks stay in name order. It is so effective that Java and other languages later adopted it.

Sorting in practice

  • sorted(items) returns a new list; items.sort() changes the list and returns None.
  • reverse=True sorts from largest to smallest.
  • key= sorts by a computed value: sorted(names, key=len) sorts by length.
  • Sort by several criteria with a tuple key: key=lambda s: (-s["mark"], s["name"]).
  • Strings sort by character codes, so capital letters come before small ones; use key=str.lower for natural order.

How it works

AlgorithmIdeaWorst-case work
Selection sortPick the smallest, move it to the frontn²
Bubble sortSwap wrong-order neighbours, pass after passn²
Insertion sortInsert each item into the sorted partn², but fast on nearly sorted lists
Python's sorted()Timsort, a refined merge and insertion sortn log n

In code

Three hand-written sorts, each checked against sorted(). Bubble sort prints the list after every pass.

sorting.py
def selection_sort(items):
    items = items.copy()
    for i in range(len(items)):
        smallest = min(range(i, len(items)), key=lambda j: items[j])
        items[i], items[smallest] = items[smallest], items[i]
    return items

def bubble_sort(items):
    items = items.copy()
    for done in range(len(items) - 1):
        for j in range(len(items) - 1 - done):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
        print("  after pass", done + 1, items)
    return items

def insertion_sort(items):
    items = items.copy()
    for i in range(1, len(items)):
        current, j = items[i], i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current
    return items

scores = [64, 25, 91, 12, 47]
print("Selection:", selection_sort(scores))
print("Bubble:")
result = bubble_sort(scores)
print("Insertion:", insertion_sort(scores))
print("All match sorted():", selection_sort(scores) == result == insertion_sort(scores) == sorted(scores))

Output

Selection: [12, 25, 47, 64, 91]
Bubble:
  after pass 1 [25, 64, 12, 47, 91]
  after pass 2 [25, 12, 47, 64, 91]
  after pass 3 [12, 25, 47, 64, 91]
  after pass 4 [12, 25, 47, 64, 91]
Insertion: [12, 25, 47, 64, 91]
All match sorted(): True

Try it yourself

Predict the list after one pass

Start from [5, 1, 4, 2]. What does each algorithm give after its first pass?

  • Bubble sort, first pass
  • Selection sort, first pass
  • Insertion sort, after placing the third item

Common mistakes

  • Forgetting that the inner loop of bubble sort can stop earlier each pass.
  • Sorting the original list by accident when you wanted a copy.
  • Writing your own sort in real projects. Use sorted() unless you are learning.

Check yourself

Question 1

1. Which sort repeatedly swaps neighbouring items?

Question 2

2. After the first pass of bubble sort, where is the largest item?

Question 3

3. Why use sorted() in real code?

Summary

  • Selection, bubble and insertion sort are simple n² algorithms.
  • They teach comparisons, swaps and nested loops.
  • Python's sorted() uses Timsort, n log n, and is the one to use.

Finished reading?

Sources: W3Schools DSA: Bubble Sort · W3Schools DSA with Python