Sorting Examples in CS Thinking

Start with the recap, study the fully worked examples, then use the practice problems to check your understanding of Sorting.

This page combines explanation, solved examples, and follow-up practice so you can move from recognition to confident problem-solving in CS Thinking.

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(n^2)$ ) to efficient (merge sort, $O(n \log n)$ ).

Putting things in order—alphabetical, numerical, by date—so they are easier to find and use.

Read the full concept explanation →

How to Use These Examples

Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.

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.

Sense of Study hint: When choosing a sorting algorithm, consider the data size and whether simplicity or speed matters more. For small datasets or learning, bubble sort is easy to understand. For large datasets, use merge sort or your language's built-in sort (usually optimized). Always clarify what 'order' means—ascending, descending, or custom.

Worked Examples

Example 1

medium

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

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

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

Unlock answer keys One Family plan — every worked solution, all subjects

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 these problems on your own first, 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

[\text{cat}, \text{ant}, \text{bee}]

alphabetically.

Example 6

easy

Sort

[4, 4, 1]

ascending.

Example 7

easy

Sort

[9, 7, 5, 3]

in descending order.

Example 8

easy

[1, 3, 2]

sorted in ascending order?

Example 9

easy

Which is generally faster for large lists: an

O(n^2)

sort or an

O(n \log 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:

[(\text{b},2),(\text{a},2),(\text{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(n \log 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(n \log 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

[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?

← Back to Sorting Practice Mode

Related Concepts

Array Algorithm Bubble Sort Merge Sort Algorithm Efficiency

Background Knowledge

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

arrayalgorithm