Sorting Algorithms | Engineering Interview Kit

Concept

Sorting is the process of rearranging data into a specific meaningful order (e.g., ascending, descending, alphabetical).
Without sorting, searching for data takes $O(N)$ time. By sorting the data, you unlock the ability to use Binary Search, dropping the search time to $O(\log N)$ .

Modern programming languages have built-in .sort() methods.
In Python: list.sort() uses Timsort (a hybrid of Merge Sort and Insertion Sort).
In JavaScript: Array.prototype.sort() uses Timsort in V8 (Chrome/Node.js) and Merge Sort in Firefox.

You will rarely, if ever, write a sorting algorithm from scratch in a production application.
However, FAANG interviews heavily test your knowledge of how these algorithms work, because they test your mastery of recursion, pointers, and time/space complexity tradeoffs.

Comparison vs Non-Comparison Sorts

There are two massive categories of sorting algorithms.

1. Comparison Sorts
These algorithms sort data by comparing two elements at a time (A < B).
Mathematically, the absolute fastest a Comparison Sort can possibly run is $O(N \log N)$ . It is mathematically impossible to break this barrier using comparisons.

$O(N^2)$ (Slow): Bubble Sort, Selection Sort, Insertion Sort.
$O(N \log N)$ (Fast): Merge Sort, Quick Sort, Heap Sort.

2. Non-Comparison Sorts
These algorithms completely break the $O(N \log N)$ barrier, achieving linear $O(N)$ time!
They do this by completely refusing to compare elements. Instead, they exploit the mathematical properties of the data (e.g., distributing numbers into buckets based on their integer values).

$O(N)$ (Blazing Fast): Counting Sort, Radix Sort, Bucket Sort.
(The catch: They only work on very specific, heavily constrained data types, usually small positive integers).

Stability

A Sorting Algorithm is considered Stable if it perfectly preserves the original relative order of identical elements.

Imagine sorting an array of objects by Age:
[{Name: Alice, Age: 25}, {Name: Bob, Age: 25}, {Name: Charlie, Age: 20}]
Sorted by Age:
[{Name: Charlie, Age: 20}, {Name: Alice, Age: 25}, {Name: Bob, Age: 25}]

Because Alice and Bob are both 25, they tied.
A Stable sort guarantees that Alice will remain in front of Bob, because Alice was originally in front of Bob in the input.
An Unstable sort might accidentally swap them (Bob, then Alice).

Stable: Merge Sort, Insertion Sort, Bubble Sort, Counting Sort.
Unstable: Quick Sort, Heap Sort, Selection Sort.

In-Place Sorting

An algorithm is In-Place if it does not require any extra memory arrays to perform the sort. It physically swaps the elements within the original array boundaries.

In-Place ( $O(1)$ Space): Quick Sort, Heap Sort, Bubble, Selection, Insertion.
Not In-Place ( $O(N)$ Space): Merge Sort (requires a massive secondary array to stitch the halves back together).

Interview Strategy

If an interviewer says “Sort this array”, your default answer should always be:
“I will use the built-in language .sort() method, which runs in $O(N \log N)$ time and $O(1)$ space.”
Only write a custom sorting algorithm if they explicitly ban the built-in method.

If they ban it, ask: “Are the numbers bounded in a very small range, like 1 to 100?”
If yes, use Counting Sort ( $O(N)$ ).
If no, write Merge Sort or Quick Sort ( $O(N \log N)$ ).

Interview Questions

Q: In JavaScript, [10, 2, 1].sort() results in [1, 10, 2]. Why is it completely broken?
A: This is a notorious JavaScript trap. By default, the native JS .sort() method forcefully converts every element into a String and sorts them alphabetically! Alphabetically, the string "10" comes before the string "2". To sort numbers mathematically in JS, you MUST pass a comparator function: array.sort((a, b) => a - b).

Q: If Quick Sort’s worst-case time complexity is $O(N^2)$ , and Merge Sort’s worst-case is $O(N \log N)$ , why is Quick Sort generally considered faster in the real world?
A: Merge Sort requires allocating and deallocating massive temporary arrays during the merge phase, which causes heavy memory overhead and cache misses. Quick Sort is an In-Place algorithm. It operates entirely within the original array using pointers. This makes it incredibly cache-friendly and extremely fast on modern CPU architectures, completely making up for its theoretical worst-case anomaly.