Engineering Fluency OS

Why This Matters

Unsorted data is hard to work with. Finding a name in a shuffled phone book, locating a product in a random catalog, or identifying duplicates in a jumbled list are all slow without order. A sorting algorithm takes a collection and arranges its elements into a defined order — typically smallest to largest.

Sorting is one of the most studied problems in computer science because it underpins so many other operations. Binary search requires sorted data. Database queries use sorted indexes. Merge operations assume sorted inputs. Understanding how different algorithms approach sorting — and why some are dramatically faster than others — is fundamental to writing efficient software.

Define Terms

Visual Model

[38, 27, 43, 3, 9, 82, 10]

[38, 27, 43, 3]

[9, 82, 10]

[38, 27]

[43, 3]

[9, 82]

[10]

[3, 9, 10, 27, 38, 43, 82]

The full process at a glance. Click Start tour to walk through each step.

Merge sort: divide the array recursively, then merge sorted halves. O(n log n) time, O(n) space.

Code Example

Code

// MERGE SORT — O(n log n) guaranteed
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

// BUILT-IN SORT with comparator
const people = [
  { name: "Charlie", age: 30 },
  { name: "Alice", age: 25 },
  { name: "Bob", age: 25 }
];

// Sort by age, then by name
people.sort((a, b) => {
  if (a.age !== b.age) return a.age - b.age;
  return a.name.localeCompare(b.name);
});
console.log(people.map(p => p.name + ":" + p.age));
// ["Alice:25", "Bob:25", "Charlie:30"]

Interactive Experiment

Try these exercises:

Implement bubble sort: compare adjacent pairs, swap if out of order, repeat until sorted. How many passes does it take?
Add a counter to merge sort to count total comparisons. How does the count grow as the array doubles?
Sort an array of strings using the built-in sort with a custom comparator for case-insensitive ordering.
What happens when you sort an already-sorted array with merge sort? Does it still do the same work?

Quick Quiz

Coding Challenge

Multi-Field Sort

Write a function called `sortStudents` that takes an array of student objects with `name` (string) and `grade` (number) properties. Sort them by grade descending (highest first), then by name ascending (alphabetical) for students with the same grade. Return the sorted array.

Loading editor...

Real-World Usage

Sorting algorithms are embedded throughout modern software:

Database indexes: Databases maintain sorted B-tree indexes so that queries like WHERE age > 25 ORDER BY name execute in milliseconds instead of scanning every row.
Search results: Search engines rank (sort) results by relevance score so the most useful pages appear first.
Spreadsheets: Every "sort by column" click in Excel or Google Sheets runs a sorting algorithm.
E-commerce: Product listings sorted by price, rating, or relevance — each requiring different comparators on the same data.
Operating systems: Process schedulers sort tasks by priority. File explorers sort files by name, date, or size.
Leaderboards: Games sort players by score in real time, often requiring efficient insertion into already-sorted data.

Sorting Algorithms