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(nlogn) 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(nlogn) 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(nlogn) 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(nlogn)).
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.