Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Sorting

Rearranging items in a collection into a defined order, such as smallest to largest or alphabetical.


Quick Answer

Rearranging items in a collection into a defined order, such as smallest to largest or alphabetical. You sort to make data easy to read and fast to use: a leaderboard from the highest score down, contacts from A to Z, a list that binary search can work on. A sort needs a key (what you compare, such as score or name) and a direction (ascending or descending). Methods differ hugely in cost: bubble sort makes about n2/2 comparisons, merge sort about nlog⁡2n.

Why This Matters

Sorted data makes other jobs cheap: the median, duplicates (they end up side by side), merging two lists and binary search all rely on order. For 100,000 items bubble sort needs about 5 billion comparisons while merge sort needs about 1.7 million, the difference between minutes and an instant. And a sort with the wrong key or direction quietly produces a list that looks ordered but answers the wrong question.

Intuitive Explanation

Picture sorting a hand of cards. You pick up one card at a time and slide it into place among the cards you already hold, which stay in order: that is insertion sort. Bubble sort works differently. Walk along the row, compare each neighboring pair and swap them if they are out of order. Sorting [5, 1, 4, 2], the first pass swaps 5 past every other card, giving [1, 4, 2, 5]: the largest value has 'bubbled' to the end. The next pass fixes the second largest, and so on.

Methods like these compare nearly every pair, about n2/2 comparisons, so doubling the list quadruples the work. Merge sort is smarter. Split the list in half, sort each half, then merge the two sorted halves by repeatedly taking the smaller front item. That costs about nlog⁡2n comparisons: for 1,000 items, about 10,000 instead of about 500,000.

Every sort needs a key and a direction. Sorting students by name gives a different list from sorting them by test score, and a leaderboard needs descending order. When two items share a key, a stable sort keeps them in their original order. That matters when you sort by one field after another: sort by name, then stably by grade, and the students within each grade stay alphabetical.

Sorting is not needed for every question about order. Finding the single highest score takes one pass of n−1 comparisons, with no rearranging at all.

Think of it like this. 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.

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


When to Use

Sort when the task needs data in order: a ranked list, alphabetical names, the median, duplicates found side by side, or a list that will be searched many times. Name the key and the direction before choosing a method. For a handful of items any method is fine; for large lists use an O(nlog⁡n) method such as merge sort. If you only need one value, such as the maximum or whether a target exists, a single pass or a search is cheaper than sorting everything.

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

How to Recognize It

Before reaching for sorting, check whether the output is the same items in a new order, and what decides that order.

  1. Does the answer contain every item from the input, only in a different order?

    Yes fits sorting, which keeps all items and only moves them. If one item or a yes/no comes back instead, you are searching.

  2. Is the question about which method to use, rather than what the ordered result is?

    Yes moves you to a specific algorithm such as Bubble Sort or Merge Sort, judged by its cost. No keeps you at sorting as a task: say what the finished list must look like.

  3. Is the data being put in order so that a later step, such as binary search or reading a leaderboard from the top, becomes fast?

    Yes is the usual reason to sort first. If the data will be searched only once, one Linear Search through the unsorted list is cheaper than sorting it.

  4. Do items with equal keys carry other data whose original order must be kept?

    Yes means you need a stable sort, such as merge sort, rather than any sort at all. No means any correct sorting method will do.

Sorting vs Searching vs Bubble Sort vs Merge Sort

Sorting is the job; bubble sort and merge sort are two ways to do it, and searching is a different job that sorting often prepares for. Ask whether the result is the whole list reordered, one found item, or a particular method.

Sorting

Meaning
Sorting is the task of putting every item of a collection into order by a chosen key and direction.
Key test
The output is the whole collection, reordered; no method is specified.
Formula
A′[0]≤A′[1]≤⋯≤A′[n−1]
Example
Sorting quiz scores [72, 95, 88, 60] in descending order gives [95, 88, 72, 60].

Searching

Meaning
Searching locates one target value in a collection, or reports that it is missing, without changing the order.
Key test
The answer is a position or 'not found', not a reordered list.
Example
Asking whether 88 is in [72, 95, 88, 60] returns index 2.

Bubble Sort

Meaning
Bubble sort is one specific sorting method that swaps neighboring items until a pass makes no swaps.
Key test
Adjacent swaps, pass after pass; about n2/2 comparisons in the worst case.
Formula
n(n−1)2 comparisons at worst
Example
[3, 1, 2]: swap 3 and 1, then 3 and 2, giving [1, 2, 3]; a second pass makes no swaps.

Merge Sort

Meaning
Merge sort is a specific sorting method that sorts each half of the list and then merges the two sorted halves.
Key test
Split in half, sort the halves, merge; about nlog⁡2n comparisons even at worst.
Formula
T(n)=2T(n/2)+O(n)
Example
[4, 2, 3, 1] becomes halves [2, 4] and [1, 3], which merge into [1, 2, 3, 4].

Formula & Notation

Worked Examples

Example 1 — Trace bubble sort pass by pass

Easy

Sort [4, 2, 5, 1] in ascending order with bubble sort. Show the list after each pass and count the comparisons and swaps.
Show the steps and the answer
  1. Pass 1: compare 4 and 2, swap → [2, 4, 5, 1]; compare 4 and 5, no swap; compare 5 and 1, swap → [2, 4, 1, 5].

    Each swap carries the larger value one place right, so the largest value, 5, finishes the pass in the last position.

  2. Pass 2, positions 0 to 2 only: 2 and 4, no swap; 4 and 1, swap → [2, 1, 4, 5].

    5 is already in its final place, so this pass needs one fewer comparison.

  3. Pass 3, positions 0 to 1: 2 and 1, swap → [1, 2, 4, 5].

    With 4 and 5 fixed, only the first pair is left to check.

  4. Count: 3 + 2 + 1 = 6 comparisons and 2 + 1 + 1 = 4 swaps.

    For n items bubble sort makes (n−1)+(n−2)+⋯+1=n(n−1)/2 comparisons; here 4⋅3/2=6.

Answer: [1, 2, 4, 5] after 3 passes, with 6 comparisons and 4 swaps.

Takeaway: Each bubble-sort pass locks the largest remaining value into place, so n items need at most n − 1 passes.

Example 2 — Looks like sorting, needs one pass

Standard

A game holds 1,000 players' scores in an unsorted array, and you need only the highest score. Compare bubble-sorting the whole array and taking the last item with a single pass that keeps the best score seen so far.
Show the steps and the answer
  1. Bubble sort cost: 1000⋅999/2=499,500 comparisons.

    Sorting puts every score in its place, far more than the question asks for.

  2. Single pass: set best = scores[0], then compare best with each of the other 999 scores, replacing it whenever a score is larger.

    To be sure of the maximum you must look at every score once, but once is enough.

  3. Compare: 999 comparisons against 499,500, which is 500 times fewer.

    A question about one extreme value needs a pass, not a rearrangement.

  4. Note when sorting does pay: printing the whole leaderboard in order, or answering many rank questions about the same scores.

    Sorting is the right tool when the order of many items matters, not just one end of the list.

Answer: Use the single pass: 999 comparisons instead of 499,500. Finding the maximum needs no sorting.

Takeaway: Before sorting, check whether the question needs the whole order or just one value.

Example 3 — Find the mistake: a sort that scrambles ties

Application

A class list is in alphabetical order: Ana (grade 10), Ben (grade 10), Cy (grade 9). Tom sorts it by grade, ascending, with selection sort (find the smallest remaining grade and swap it to the front). He gets Cy 9, Ben 10, Ana 10 and says: "Sorted by grade is sorted by grade. The order of Ana and Ben doesn't matter." The teacher wanted names to stay alphabetical within each grade. Find the mistake and correct it.
Show the steps and the answer
  1. Trace selection sort: the smallest grade is Cy's 9 at index 2; swapping it with index 0 sends Ana from the front to the back, giving Cy 9, Ben 10, Ana 10.

    A long-distance swap can jump an item over others with the same key, which is how equal items change order.

  2. Compare with what the teacher needed: within grade 10, Ana should come before Ben.

    The grades are in order, but the alphabetical order the list already had is broken, and Tom's claim ignores that requirement.

  3. Switch to a stable sort, such as insertion sort or merge sort, which never moves an item past an equal one.

    A stable sort keeps items with equal keys in their original relative order.

  4. Trace insertion sort: start with Ana 10; insert Ben 10 after Ana, since 10 is not less than 10; insert Cy 9 in front of both, giving Cy 9, Ana 10, Ben 10.

    Only a strictly smaller grade moves an item forward, so Ben stays behind Ana.

Answer: Use a stable sort: Cy 9, Ana 10, Ben 10.

Takeaway: When items with equal keys carry other data, decide whether their order must survive, and use a stable sort if it must.

Where You'll See It

  • Sorting a hand of playing cards

    Picking up cards and inserting each into its correct spot among the ones you've already ordered is exactly insertion sort, putting the hand in order so you can find a card fast.

  • Alphabetizing a bookshelf

    Arranging books A-to-Z is sorting by a key (the title); once sorted, finding a book becomes a quick binary-search-style scan instead of checking every shelf.

  • Leaderboard high scores

    A game shows scores from highest to lowest by sorting the score list in descending order, making the top players easy to read at a glance.

Common Mistakes

  1. The slip: All sorting algorithms are basically equally fast.

    Why it's tempting: They all produce the same sorted result, so they seem interchangeable.

    Instead: Sorting algorithms differ a lot in speed: bubble sort is O(n2), while merge sort is O(nlog⁡n). On large data that difference is enormous.

  2. The slip: Sort order doesn't need to be stated; sorting just means 'in order'.

    Why it's tempting: 'Sorted' sounds unambiguous in everyday speech.

    Instead: You must specify the order (ascending vs. descending) and the key. The same data 'sorted' can come out reversed depending on what you asked for.

  3. The slip: When two items have equal keys, it doesn't matter which comes first.

    Why it's tempting: If the keys are equal, the result looks identical either way.

    Instead: Stability matters when equal-key items carry different extra data: a stable sort keeps their original relative order, which is needed when sorting by one field after another.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Sort the test scores [72, 95, 68, 95, 81] in descending order (largest first). What is the sorted list, and which score sits at index 2?

    Hint: Descending means start with the biggest value. Indexes start at 0.

  2. Sort these words alphabetically, A to Z: pear, apple, fig, banana, cherry. Which word ends up in the middle?

    Hint: Compare first letters. All five words start with different letters.

  3. Records are listed in this order: (Ana, B), (Ben, A), (Cy, B), (Dee, A). A stable sort by grade puts A before B. Write the result.

    Hint: A stable sort keeps records with equal grades in their original order.

  4. For n=1,000,000 items, bubble sort makes about n2 comparisons and merge sort about nlog⁡2n. Using log⁡2n≈20, about how many times more comparisons does bubble sort make?

    Hint: Write n2 and 20n as powers of ten, then divide.

  5. You need only the lowest of 500 temperature readings, just once. Should you sort the list first, or use a different algorithm that scans it once?

    Hint: Count the work each way. Does the question need every item in order?

  6. Asked to list runners from fastest to slowest, a student sorts their times in descending order, 14.2 s, 13.5 s, 12.8 s, and says 14.2 s is the fastest. Correct the mistake.

    Hint: In a race, is a faster runner's time bigger or smaller?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Why can no comparison sort beat about nlog⁡2n comparisons?

A list of nn different items can be arranged in n!n! ways, and each comparison has only two outcomes, so at best it halves the arrangements still possible. Telling all n!n! apart needs at least log⁡2(n!)\log_2(n!) comparisons, which grows like nlog⁡2nn \log_2 n. For 10 items that is log⁡2(3,628,800)≈21.8\log_2(3{,}628{,}800) \approx 21.8, so any comparison sort needs at least 22 comparisons on its worst input.

Is there any way to sort faster than nlog⁡n?

Yes, if you do not sort by comparing. Counting sort works when keys are small whole numbers: to sort 1,000 test scores from 0 to 100, count how many students got each score, then write the scores out in order. That takes about 1,000 + 101 steps instead of about 10,000 comparisons. The catch is that it needs a known, limited range of keys, so it cannot sort arbitrary names.

Why does JavaScript sort [10, 9, 1] into [1, 10, 9]?

With no comparison function, JavaScript's sort turns the numbers into text and compares them character by character, so '10' comes before '9' just as 'ba' comes before 'c'. The key is the text, not the number. Passing a comparison, as in list.sort((a, b) => a - b), makes it compare numerically and gives [1, 9, 10]. Always check what key your language compares by default.

Learning Path

← Before

ArrayAlgorithm
Sorting

You are here

You need Array (items at index positions) and Algorithm (steps you can trace) first. Sorting adds rearranging a whole collection by a key and a direction, and shows that methods with the same output can cost very different amounts. Next, Bubble Sort and Merge Sort are traced step by step, and Algorithm Efficiency explains why n2 and nlog⁡n grow so differently.

See Also