Sorting is a core building block in coding interviews and production systems, including ranking and organizing data shown in the One Drop app. Interviewers use this topic to test whether you understand algorithmic trade-offs rather than just memorizing names.
Explain the differences between common sorting algorithms such as bubble sort, insertion sort, merge sort, quicksort, and heapsort.
Your answer should cover:
You do not need to derive the algorithms from scratch, but you should be able to compare them clearly, explain the main idea behind each one, and discuss practical trade-offs. A strong answer also mentions why some simple algorithms are still useful on small or nearly sorted inputs, and why asymptotically faster algorithms dominate at scale.
Sorting algorithms differ mainly in how their running time grows with input size. Simple comparison sorts like bubble sort and insertion sort are typically O(n^2), while more efficient general-purpose sorts like merge sort, quicksort, and heapsort are O(n log n) on average or in the worst case depending on the algorithm.
n = len(arr)
# Bubble / insertion: often O(n^2)
# Merge / heap: O(n log n)
# Quick: average O(n log n), worst O(n^2)
An in-place sort modifies the array using little extra memory, which matters when data is large. Merge sort usually needs additional O(n) space, while quicksort and heapsort are more memory-efficient, though recursive quicksort still uses stack space.
A stable sorting algorithm preserves the relative order of elements with equal keys. This matters when records have multiple fields, such as sorting One Drop member events by timestamp after already grouping by priority.
records = [(2, 'a'), (1, 'x'), (2, 'b')]
# Stable sort by first field keeps 'a' before 'b'
Some algorithms perform especially well on partially sorted data. Insertion sort is a classic example because it only shifts elements that are out of place, making it efficient for small or nearly sorted inputs.
An algorithm with strong worst-case guarantees is not always the fastest in practice. Quicksort is often very fast because of cache behavior and low constant factors, but merge sort offers predictable O(n log n) performance and stability.
