Sorting Examples: 48 Problems with Answers

Worked examples of Sorting to try before you open each solution, then practice problems with answers.

Worked Examples

Example 1

medium
Sort the list [5, 2, 8, 1, 9] using bubble sort. Show the first two passes.
Show solution

Answer

After pass 1: [2,5,1,8,9]. After pass 2: [2,1,5,8,9]. Final: [1,2,5,8,9].

First step

1.
Step 1: Pass 1 — compare adjacent pairs and swap if needed: (5,2)→swap→[2,5,8,1,9], (5,8)→ok, (8,1)→swap→[2,5,1,8,9], (8,9)→ok. After pass 1: [2,5,1,8,9].

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

hard
Compare bubble sort and merge sort in terms of time complexity. When would you choose one over the other?

Example 3

easy
Apply one pass of selection sort to [4,2,6,1]: find the minimum and swap it to position 0.

Example 4

medium
A naive bubble sort runs all n−1 passes even when sorted by pass 2. Name one optimization.

Example 5

hard
Use heapsort intuition: building a max-heap of n=4 elements takes how many comparisons (tight upper bound)?

Example 6

challenge
Argue why timsort (hybrid merge + insertion) often beats pure merge sort on real-world data.

Practice Problems

Try each one, then open the solution to compare your method.

Example 1

medium
Sort [4, 1, 3] using insertion sort. Show each step.

Example 2

medium
You have a list of exam scores that is already sorted except one new score was added at the end. Would insertion sort or bubble sort be a better choice, and why?

Example 3

easy
Sort the list [3,1,2] into ascending order.

Example 4

easy
Sort [5,2,8,1] in ascending order.

Example 5

easy
Sort the words [cat,ant,bee] alphabetically.

Example 6

easy
Sort [4,4,1] ascending.

Example 7

easy
Sort [9,7,5,3] in descending order.

Example 8

easy
Is [1,3,2] sorted in ascending order?

Example 9

easy
Which is generally faster for large lists: an O(n2) sort or an O(nlog⁡n) sort?

Example 10

easy
After sorting, the smallest element of [6,2,9] is at which end of an ascending list?

Example 11

medium
Sort [3,1,4,1,5] ascending and report the value at index 2 (0-indexed).

Example 12

medium
You must repeatedly search a 1,000,000-item list many times. Should you sort once first, then binary-search? Why?

Example 13

medium
Sort the pairs by their number key: [(b,2),(a,2),(c,1)]. With a stable sort, what is the order of the two key-2 items?

Example 14

medium
How many adjacent comparisons does one full pass of bubble sort make on a list of 6 elements?

Example 15

medium
Sort [10,−3,0,7,−3] ascending.

Example 16

medium
What is the worst-case time complexity of bubble sort, and on what input does it occur?

Example 17

medium
A program sorts then must keep records with equal scores in submission order. Which property must the sort have?

Example 18

medium
Sort [1,2,3,4,5] with bubble sort using the early-exit optimization. How many full passes are needed?

Example 19

medium
After sorting [8,3,5,4] ascending, what is the median (average of the two middle values)?

Example 20

challenge
Prove the minimum number of comparison-based operations cannot beat O(nlog⁡n) in the worst case. State the bound and one-line reason.

Example 21

challenge
A list of 8 items is already sorted. Compare the number of comparisons for optimized bubble sort vs merge sort.

Example 22

challenge
You sort 1 billion 64-bit integers. Argue why a stable O(nlog⁡n) sort with O(n) extra memory may still be the wrong choice, and name what to check.

Example 23

easy
Sort [7,3,5] ascending.

Example 24

easy
Sort [8,8,2,5] ascending.

Example 25

easy
Sort [12,5,7,1] in descending order.

Example 26

easy
How many elements does [3,1,2] have? After sorting, what is at index 1?

Example 27

easy
Is [5,5,5] already sorted in ascending order? Yes or no.

Example 28

medium
Sort [5,2,9,1,7] ascending and report the median.

Example 29

medium
How many comparisons does insertion sort perform in the WORST case on a list of size 4?

Example 30

medium
A merge sort splits a list of 8 in half repeatedly. How deep does the recursion go?

Example 31

medium
Merge two sorted lists [1,4,7] and [2,3,8]. Give the result.

Example 32

medium
A stable sort applied to [(2,A),(1,B),(2,C)] by first key gives what order?

Example 33

medium
Quicksort's average-case complexity?

Example 34

medium
Sort [3.1,2.7,1.4,1.6] ascending.

Example 35

medium
After ascending sort, the LARGEST element of [6,2,9,4] is at which index (0-based)?

Example 36

medium
Counting sort works in O(n+k) where k is the value range. For what kind of input is it a poor choice?

Example 37

medium
Sort [3,−1,0,−2,5] ascending.

Example 38

medium
Why might you want to sort even though searching unsorted lists is O(n) already?

Example 39

hard
On a list of size 16, how many comparisons does merge sort do in the worst case (approx)?

Example 40

hard
Quicksort hits worst case on already-sorted input when pivot = first element. What is the complexity?

Example 41

hard
Why is radix sort sometimes faster than merge sort despite both being efficient?

Example 42

challenge
Three sorted lists of length 5 each are merged. Minimum number of comparisons in the worst case?

What to focus on

Core idea: Different sorting algorithms have different efficiency trade-offs and work better in different situations.

Common stuck point: Stable sort preserves original order of equal elements; unstable doesn't.

Ask yourself: Must the whole collection be rearranged into order by some key, ascending or descending?

Concept recap

Rearranging items in a collection into a defined order, such as smallest to largest or alphabetical. Sorting is one of the most studied problems in computer science, with algorithms ranging from simple (bubble sort, O(n2)) to efficient (merge sort, O(nlog⁡n)).

Lining up a class by height for a photo is sorting. Neighbors can keep swapping until no pair is out of order (bubble sort), or the class can split in two, line up each half, and merge the two lines by sending forward the shorter front person each time (merge sort). A computer cannot see the whole line at once; it compares two people at a time.

Read the full lesson on Sorting

Background knowledge

These ideas may be useful before you work through the harder examples.

arrayalgorithm