Click image to open full size
Computer Science
Sorting Algorithms
How Computers Put Things in Order
Related Tools
Related Labs
Related Worksheets
Related Cheat Sheets
Sorting algorithms are step by step methods computers use to arrange data into a chosen order, such as numbers from smallest to largest or names from A to Z. Sorting matters because organized data is faster to search, compare, display, and analyze. Every app that ranks search results, sorts files by date, or organizes a leaderboard depends on sorting. Different algorithms solve the same task in different ways, so choosing the right one can greatly affect speed.
Key Facts
- A sorting algorithm takes an input list and returns the same items in a chosen order, such as ascending or descending.
- Comparison sorts decide order by comparing pairs of values, such as asking whether a < b.
- Time complexity estimates how running time grows with input size n, such as O(n), O(n log n), or O(n^2).
- Bubble sort repeatedly swaps neighboring items that are out of order and has worst case time O(n^2).
- Merge sort splits the list, sorts the pieces, and merges them, giving time O(n log n).
- A stable sort keeps equal items in their original relative order.
Vocabulary
- Algorithm
- An algorithm is a precise set of steps used to solve a problem or complete a task.
- Array
- An array is an ordered collection of values stored so each value can be accessed by its position.
- Comparison
- A comparison is a test between two items to decide which should come first in the sorted order.
- Time Complexity
- Time complexity describes how the number of steps an algorithm takes grows as the input size increases.
- Stable Sort
- A stable sort preserves the original order of items that have equal sorting keys.
Common Mistakes to Avoid
- Thinking all sorting algorithms are equally fast is wrong because their running times can grow very differently as n increases.
- Ignoring input size is wrong because an algorithm that works fine for 20 items may be too slow for 20 million items.
- Confusing O(n log n) with O(n^2) is wrong because O(n^2) grows much faster for large n.
- Forgetting stability is wrong because equal values may carry extra information, such as two students with the same score who should remain in original order.
Practice Questions
- 1 A bubble sort makes one comparison for each neighboring pair in a list of 8 items during its first pass. How many comparisons are made in the first pass?
- 2 Merge sort has running time proportional to n log2 n. Estimate n log2 n for n = 16 and compare it with n^2 for n = 16.
- 3 A list of student records is sorted by last name and then sorted by grade using a stable sorting algorithm. Explain why stability can help preserve alphabetical order among students with the same grade.