Lecture notes · Programming in Python · Lecture 24

Sorting Algorithms

MIT 6.100L Intro to CS and Programming using Python, lecture 24, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains why sorting a list first can pay off when you search it many times, and it starts a tour of sorting methods, from a very bad one to bubble sort.

Key ideas

Binary search is much faster than linear search, but it only works on a list that is already sorted. Using it on an unsorted list gives wrong answers. 1:18
Sorting a list takes time, so it only pays off when you search the same list many times. The cost of one sort is spread across all those searches. 3:48
No sorting method can beat theta of n time, because you must look at each element at least once. So sorting can never be faster than that. 3:04
Bogo sort is a very bad method. It shuffles the list at random and checks whether it is sorted, then repeats. In the worst case it may never finish. 5:15
Bubble sort compares neighboring elements and swaps them when they are out of order. Each pass moves the largest remaining element to the end of the list. 8:10

Words to know

binary search: A fast way to find an item in a sorted list. It checks the middle, then throws away half the list, and repeats.
complexity: How much time or work a method takes, and how that grows as the list gets longer.
amortize: To spread a one-time cost across many uses, so each use costs less.
swap: To exchange the positions of two items in a list.

Example

Think of a deck of cards you will look through many times to find different cards. Sorting the deck once takes effort, but after that each search is quick, so the effort pays off. If you only needed one card, flipping through the unsorted deck would be faster.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains two simple ways to put a list in order, bubble sort and selection sort, and why bubble sort can get slow on big lists.

Key ideas

In bubble sort, each pass compares neighboring pairs and swaps them when they are out of order. Each pass carries the biggest remaining element to the end of the list. 10:39
A Boolean flag is a yes-or-no switch that records whether any swap happened during a pass. When a pass makes no swaps, the list is sorted and the loop can stop. 11:01
The inner loop starts at index 1 and compares each element with the one before it. Starting at 0 would look at a position before the list begins, which causes an index out of bounds error. 11:23
In the worst case, where the list is completely backward, bubble sort does about n times n steps. That is why the lesson calls it inefficient. 14:40
Selection sort decides which element belongs at index 0, then index 1, then index 2, and so on. Each time it scans the rest of the list for the smallest element, so it does less work than bubble sort because the finished spots are not checked again. 16:01

Words to know

swap: to trade places, so that two items switch positions in the list.
Boolean flag: a simple yes-or-no switch in code, here used to remember whether a swap happened.
index out of bounds: an error that happens when code tries to reach a position that does not exist in the list, like position -1.
worst case: the most difficult input the method could face, used to judge how slow it can get.

Example

Imagine a line of people who need to stand in order of height. You walk down the line, and whenever two neighbors are in the wrong order, you swap them. After one trip down the line, the tallest person is at the end, and you repeat until nobody needs to move.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows why the simple sorting method is slow, why small tweaks don't fix it, and how merge sort splits the problem in half to do better.

Key ideas

Selection sort takes theta of L squared steps, where L is the list length. Theta is a way of saying how the work grows as the list gets bigger. 20:19
Counting the comparisons gives L + (L-1) + ... + 1, which works out to about L squared over 2. Dropping the constants leaves theta of L squared. 22:27
Keeping track of the smallest value and swapping only once at the end is a useful tweak, but it still makes all the comparisons, so the complexity is still theta of L squared. 25:50
Small speed-ups cannot drop the work into a lower complexity class. A different way of thinking about the problem is needed. 27:20
Merge sort uses divide and conquer. It splits the list in half, recursively, and then merges sorted pieces in a smart way. 28:02

Words to know

theta: A way to describe how the amount of work grows as the input gets bigger, ignoring small constant parts. Theta of L squared means the work grows roughly with the square of the list length.
selection sort: A sorting method that repeatedly finds the smallest remaining item and puts it in the next spot in the list.
divide and conquer: A problem-solving strategy that breaks a big problem into smaller parts, solves each part, and then combines the results.
recursively: Doing something again and again by having a process call a smaller version of itself, such as splitting a list over and over until the pieces are tiny.

Example

Think of sorting a deck of cards by checking every card against every other card one at a time. Now think of splitting the deck into two piles, sorting each pile, and then merging the piles by always taking the smaller card on top. The second way handles a big deck much faster, because you never have to compare every card with every other card.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how merge sort works: it splits a messy list into tiny pieces, then joins sorted pieces back together by comparing only the front items.

Key ideas

The merge step combines two lists that are already sorted. You compare the first element of each list, take the smaller one, and repeat until the lists are used up. 30:21
Because each merge only looks at the front items, it touches every element just once. The lesson says this costs theta of n, which means the work grows in step with the list length. 31:05
Merge sort splits the big unsorted list in half again and again until each piece holds one element. A one-element list is already sorted, so the pieces are then merged back up in pairs. 32:11
The recursive version always works on the left side first, like Fibonacci. It keeps going left until it reaches a base case, which is the simplest case that needs no further splitting, and only then handles the right side. 36:06

Words to know

merge: Joining two sorted lists into one bigger sorted list by repeatedly taking the smaller front item.
sublist: A smaller list that is part of a bigger list. Merge sort makes sublists by cutting the original list in half.
base case: The simplest version of a problem, which can be answered directly without making the problem smaller again. In merge sort, a list with one element is the base case.
index: A number that tells you which position in a list you are looking at, so you can pick the next element without copying the list.

Example

Imagine two piles of playing cards, each already sorted from low to high. To make one sorted pile, you look only at the top card of each pile, place the lower card on your new pile, and repeat until one pile is empty, then add the rest of the other pile. You never need to look through the whole pile again.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–47:27

This part explains how merge sort works: it splits a list in half again and again, then merges the sorted pieces back together, and why that makes it fast.

Key ideas

The merge step looks at the front element of each of two sorted lists, copies the smaller one into a new list, and moves that pointer forward. When one list runs out, the leftover elements of the other list are copied over. 40:00
The merge step looks at each element only once in a single pass, so its cost grows in step with the length of the list. 41:23
Merge sort is recursive: a list with zero or one element is already sorted, so it is returned as is. Otherwise, the list is split in half, each half is sorted by the same method, and then the two sorted halves are merged. 41:44
Splitting a list in half repeatedly takes about log n levels. Each level does merge work on all n elements, so the whole sort takes about n log n steps. 45:25
The lesson says n log n is the fastest a sorting algorithm can be, and that complexity analysis like this helps you decide whether a program design is likely to be slow before you write it. 46:29

Words to know

merge: Combining two lists that are already sorted into one bigger sorted list, by repeatedly taking the smaller front element.
recursion: When a function solves a problem by calling itself on smaller pieces of that same problem.
base case: The simple situation where a recursive function stops calling itself and just returns an answer. Here, a list that is empty or has one element.
integer division: Dividing and throwing away any remainder or fraction, so the result is a whole number. For example, 15 divided by 2 gives 7, not 7.5.

Example

Imagine two piles of playing cards, each already sorted from lowest to highest. To combine them, you look at the top card of each pile, place the lower one on a new pile, and repeat until both piles are used up. Merge sort does this same kind of combining, and it keeps splitting the cards into smaller piles until each pile holds a single card.

3 checked practice questions for this part are in the app.

← Lecture 22: Big Oh and Theta

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York