Sorting Overview

Sorting Overview

So you want to learn sorting algorithms? Great choice. Sorting is one of the most fundamental operations in computer science. Think about it — every time you sort contacts alphabetically, order search results by relevance, or arrange files by date, sorting is happening behind the scenes.

Sorting matters because it makes everything else faster. A sorted array lets you search in O(log n) instead of O(n). Many other algorithms — like finding duplicates or merging datasets — depend on sorted input. Mastering sorting is like unlocking a superpower for problem solving.

Comparison vs Non-Comparison Sorts

Sorting algorithms fall into two main camps. Comparison sorts determine order by comparing pairs of elements. Bubble sort, merge sort, and quick sort all work this way. The best any comparison sort can do is O(n log n) — that's a mathematical limit, not just a skill issue.

Non-comparison sorts sidestep comparisons entirely by using properties of the keys themselves, like counting occurrences or sorting digit by digit. Algorithms like counting sort and radix sort can beat O(n log n), but they come with restrictions on what data they can handle.

const comparisonSorts = ["Bubble Sort", "Selection Sort", "Insertion Sort", "Merge Sort", "Quick Sort"];
const nonComparisonSorts = ["Counting Sort", "Radix Sort", "Bucket Sort"];
console.log("Comparison sorts:", comparisonSorts.length);
console.log("Non-comparison sorts:", nonComparisonSorts.length);

Stability in Sorting

A sorting algorithm is stable if it preserves the relative order of elements with equal keys. Imagine sorting students by grade — a stable sort keeps students with the same grade in their original order. That's often exactly what you want.

Unstable sorts might shuffle equal elements around. Selection sort is unstable, for example, because its swaps can jump elements far apart. Merge sort is stable by design, which is one reason it's so popular in real-world applications.

Quick Reference Table

Here's your cheat sheet for the main sorting algorithms you'll encounter. Keep this handy when deciding which one to use.

const sortingAlgorithms = [
  { name: "Bubble Sort", time: "O(n²)", space: "O(1)", stable: true },
  { name: "Selection Sort", time: "O(n²)", space: "O(1)", stable: false },
  { name: "Insertion Sort", time: "O(n²)", space: "O(1)", stable: true },
  { name: "Merge Sort", time: "O(n log n)", space: "O(n)", stable: true },
  { name: "Quick Sort", time: "O(n log n) avg", space: "O(log n)", stable: false },
  { name: "Counting Sort", time: "O(n + k)", space: "O(k)", stable: true },
  { name: "Radix Sort", time: "O(d × n)", space: "O(n + k)", stable: true }
];
sortingAlgorithms.forEach(algo => {
  console.log(`${algo.name}: ${algo.time} time, ${algo.space} space`);
});