What are sorting algorithms in computer science?
A sorting algorithm rearranges elements into a defined order, usually ascending or descending according to a comparison key. The appropriate algorithm depends on the data type, size, distribution, memory limits, and whether stability is required.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Concepts
-
In-place sort: Reorders the input using little or no additional storage, usually O(1) auxiliary space.
-
Stable sort: Preserves the original relative order of elements with equal keys. This matters when sorting records by one field after they have already been sorted by another.
-
Comparison sort: Compares elements to determine their order. Comparison-based sorting requires at least Ω(n log n) time in the worst case.
-
Non-comparison sort: Uses properties of the data, such as numeric ranges or digit representation, to potentially achieve better than O(n log n) performance.
-
Auxiliary space below excludes the original input but includes temporary arrays and the recursion stack.
Common Sorting Algorithms
| Algorithm | Best time | Average time | Worst time | Auxiliary space | Stable? | In-place? |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) with early exit | O(n²) | O(n²) | O(1) | Yes | Yes |
| Insertion sort | O(n) for nearly sorted data | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) average, O(n) worst | No | Yes |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | With careful implementation | No |
| Radix sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | With stable passes | No |
| Bucket sort | O(n + k) | O(n + k) | O(n²) with poor distribution | O(n + k) | Not guaranteed | No |
Here, k is the number of possible keys or buckets, and d is the number of digits or positions processed.
-
Bubble sort repeatedly swaps adjacent inverted elements. Its best case occurs when an early-exit implementation detects that the array is already sorted.
-
Insertion sort grows a sorted prefix by shifting larger elements and inserting each new element into its correct position. It is effective for small or nearly sorted inputs.
-
Selection sort repeatedly selects the smallest remaining element and moves it into place. It performs a predictable number of comparisons but is not stable.
-
Merge sort divides the input and merges sorted halves. Its O(n log n) time comes from log n levels of linear merging, while its O(n) space holds temporary arrays and recursive slices.
-
Quicksort partitions around a pivot and recursively sorts each partition. Randomized pivots provide expected O(n log n) performance, but adversarially chosen pivots can cause O(n²) time and O(n) recursion-stack space.
-
Heap sort builds a binary max-heap and repeatedly extracts the largest remaining element. Building the heap takes O(n), and each extraction takes O(log n), so the total is O(n log n) with O(1) auxiliary space.
-
Counting sort counts key frequencies and reconstructs the ordered output in O(n + k) time, using O(n + k) additional space.
-
Radix sort processes keys position by position. With stable passes, d positions and k possible digit values produce O(d(n + k)) time and O(n + k) auxiliary space.
-
Bucket sort distributes keys among buckets and sorts within each bucket. Its average case assumes a reasonably uniform distribution; poor distributions can lead to O(n²) time.
Example Walkthrough
For merge sort with [5, 2, 4, 6, 1, 3]:
-
Split the list into
[5, 2]and[4, 6, 1, 3]. -
Split again into
[5],[2],[4], and[6, 1, 3]. -
Sort and merge the small groups into
[2, 5],[4, 6], and[1, 3]. -
Merge
[2, 5]and[4, 6]into[2, 4, 5, 6]. -
Merge that result with
[1, 3]to obtain[1, 2, 3, 4, 5, 6].
Python’s Built-in Sorting
Python 3.12 uses Powersort for sorted() and list.sort(). Powersort is stable, has O(n log n) worst-case time, and runs in O(n) time on already sorted or reverse-sorted input.
-
sorted()returns a new list and leaves the original unchanged. -
list.sort()modifies the list in place and returnsNone. -
The
keyparameter controls which value is compared. -
Stability preserves the order of records with equal keys, such as two records with the same secondary sort value.
Interview Tips
-
Clarify whether the input may be mutated and whether stable ordering is required.
-
Consider the data distribution: insertion sort may outperform O(n log n) algorithms for small or nearly sorted inputs.
-
Explain the time and space trade-offs, including quicksort’s O(n) worst-case recursion stack and merge sort’s O(n) temporary storage.
-
Define behavior for empty inputs, one-element inputs, duplicates, negative values, and already sorted or reverse-sorted data.
-
Avoid claiming that every sorting algorithm has an Ω(n log n) lower bound; that lower bound applies to comparison sorts.