Sorting CS Thinking Example 4

Follow the full solution, then compare it with the other examples linked below.

Example 4

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?

Solution

  1. 1
    Step 1: Insertion sort is a better fit because the list is already nearly sorted. The new score can be moved left until it reaches the correct position.
  2. 2
    Step 2: Bubble sort would still need repeated passes and extra comparisons, so it does more work than necessary for this situation.

Answer

Insertion sort is the better choice because it handles nearly sorted data efficiently by inserting the new value into the right position.
Choosing a sorting method depends on the input shape, not just the final goal. Nearly sorted lists are a case where insertion sort is often more practical than bubble sort.

About Sorting

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

Learn more about Sorting →

More Sorting Examples

Example 1 medium

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

Example 2 hard

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

Example 3 medium

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

← All Sorting Examples Sorting Concept