Introduction to Sorting
Explore the fundamentals of sorting algorithms, including comparison-based and non-comparison-based methods, their time and space complexity, and stability. Understand why sorting matters for efficient data handling and how JavaScript's built-in .sort() function operates with custom comparison functions.
We'll cover the following...
Imagine a librarian who receives a hundred returned books at closing time. Every book has a shelf number, but they arrive in no particular order. The librarian could place each book wherever there is space and search through all one hundred books the next time someone asks for one. Or the librarian could spend a few minutes placing them in order by shelf number, after which every future retrieval becomes much faster.
This is the fundamental motivation for sorting in computing. Sorting is not an end in itself. It enables faster operations later.
Sorting is the process of arranging elements in a collection into a defined order, such as ascending, descending, or alphabetical order.
The comparison criterion must define a total order. For any two elements a and b, exactly one of a < b, a === b, or a > b must be true.
This is why JavaScript’s default Array.prototype.sort() can produce unexpected results if no comparison function is provided. For example, [1, 30, 4, 21].sort() becomes [1, 21, 30, 4] because elements are converted to strings and compared lexicographically by default.
Why does sorting matter?
Sorted data enables operations that are inefficient or impractical on unsorted data.
Sorting enables faster searching
Sorting allows algorithms like binary search to work, reducing search time from