What is sorting?

AlgorithmsJunior~4 min read

Sorting is the process of ordering the elements of a collection (arrays, lists) by a given key or comparison rule. It allows faster searching, aggregation, and processing of data. Efficient comparison-based algorithms sort in O(n log n), and the choice of a specific algorithm depends on the requirements for stability, memory, and data size.

Detailed breakdown

Key goals and terms

Purpose: order elements by a key (number, string, date, composite key) to speed up searching, joining, and analytics.
Stability: a stable sort preserves the original relative order of elements with equal keys.
In-place vs out-of-place: in-place uses O(1) extra memory (except the stack), out-of-place requires extra arrays.
Internal vs external: internal (in-memory) sorting runs in RAM; external sorting handles data that does not fit in memory (files, streams), usually based on merge sort with multi-way merging.
Comparison-based vs non-comparison: comparison-based sorting uses only comparisons (lower bound Ω(n log n)); non-comparison sorting (counting, radix) requires additional assumptions about the keys and can be faster - O(n + k).

Commonly used algorithms

Insertion Sort: O(n^2) average and worst case, O(n) best case (nearly sorted); memory O(1); stable; in-place. Good for n ≤ ~50-200 or nearly sorted data.
Merge Sort: O(n log n) always; memory O(n); stable; out-of-place. Good for large data, when stability is required, for external sorting, and for linked lists.
Quick Sort: average O(n log n), worst case O(n^2); memory O(log n) due to recursion; unstable; in-place. Often the fastest in practice with a good pivot choice and optimizations.
Heap Sort: O(n log n) average/worst case; memory O(1); unstable; in-place. Predictable worst-case complexity with no extra memory.
Counting Sort: O(n + k); memory O(n + k); stable with a correct implementation; out-of-place. Works for integer keys with a bounded range k.
Radix Sort: O(d·(n + b)), where d is the number of digits and b is the base; memory O(n + b); usually stable; out-of-place. For fixed-format numbers/strings.

Choosing an algorithm in practice

Stability is required: Merge Sort/Timsort/Counting/Radix.
Minimal memory: Quick Sort (in-place) or Heap Sort.
Nearly sorted data: Insertion Sort or a hybrid (for example, Timsort).
Bounded range of integer keys: Counting/Radix (very fast).
Very large data outside memory: external sorting (multi-way merge).

Code examples

JavaScript: sorting with a comparator (stable by field)

Important rule: a comparator must return a negative/zero/positive number, not true/false.

const users = [
  { name: 'Maria', age: 25 },
  { name: 'Oleh', age: 20 },
  { name: 'Bob', age: 25 },
  { name: 'Alice', age: 20 }
];

// First by age ascending, then by name using locale-aware comparison (stable)
users.sort((a, b) => {
  if (a.age !== b.age) return a.age - b.age;
  return a.name.localeCompare(b.name, 'en');
});

const nums = [10, 2, 3, 1];
// Correct: numeric sort
nums.sort((a, b) => a - b);

// Incorrect: returns true/false, which can give an incorrect order
// nums.sort((a, b) => a < b);

// Note: modern JS implementations (ES2019+) make Array.prototype.sort stable.

Quicksort (QuickSort) in-place

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const pivot = arr[(left + right) >> 1];
  let i = left, j = right;
  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++; j--;
    }
  }
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
  return arr;
}

console.log(quickSort([3, 6, 1, 5, 2, 4]));

Merge sort (MergeSort), stable

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      res.push(left[i++]);
    } else {
      res.push(right[j++]);
    }
  }
  return res.concat(left.slice(i), right.slice(j));
}

console.log(mergeSort([5, 2, 4, 6, 1, 3]));

Frequent mistakes

The comparator returns true/false instead of a number (JS). It should return: a - b or use localeCompare.
Ignoring locale when comparing strings: case, diacritics, numeric sorting of strings ('10' < '2'). Use localeCompare or normalize the strings beforehand.
Choosing O(n^2) algorithms on large data without a real need (Bubble/Selection/Insertion on unsorted arrays).
Not thinking through memory: Merge Sort requires O(n) extra memory; for very large arrays, use external merging or in-place approaches.
Lack of stability where the original order of equal keys matters (for example, multi-criteria sorting).
A poor pivot choice in QuickSort can lead to O(n^2). Use the median of three, a random pivot, or hybridization.

Quick complexity cheat sheet

Algorithm	Average	Worst	Memory	Stable	In-place
Bubble	O(n^2)	O(n^2)	O(1)	Yes	Yes
Insertion	O(n^2)	O(n^2)	O(1)	Yes	Yes
Selection	O(n^2)	O(n^2)	O(1)	No	Yes
Merge	O(n log n)	O(n log n)	O(n)	Yes	No
Quick	O(n log n)	O(n^2)	O(log n)	No	Yes
Heap	O(n log n)	O(n log n)	O(1)	No (usually)	Yes
Counting	O(n + k)	O(n + k)	O(n + k)	Yes (with prefix sums)	No
Radix	O(d·(n + b))	O(d·(n + b))	O(n + b)	Usually yes	No

Summary

Sorting is a fundamental tool for working with data. Understanding stability, asymptotics, memory requirements, and the nature of keys helps you choose an algorithm deliberately: Timsort/Merge for stability, Quick/Heap for in-place sorting, Counting/Radix for integer ranges. In application code, it is especially important to define the comparator correctly and account for locale/key type.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.