Suggest an edit

Improve this article

Refine the answer for “What is sorting?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## What is sorting?

### Short answer

**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

1. 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.
2. 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.
3. 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.
4. Heap Sort: O(n log n) average/worst case; memory O(1); unstable; in-place. Predictable worst-case complexity with no extra memory.
5. 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.
6. 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.

```js
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

```js
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

```js
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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1002 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.