Sorting Algorithm

Sorting algorithms arrange elements in order—quicksort, merge sort, and heapsort are common—with complexity ranging from O(n log n) to O(n²).

Purpose

To order unordered data, the basis of searching, deduplication, and display.

Mechanism

Comparison sorting has an O(n log n) lower bound. Quicksort averages O(n log n), worst case O(n²), in place. Merge sort is O(n log n), stable, but needs O(n) space. Heapsort is O(n log n) in place. Counting/radix sorts are non-comparison and can be O(n). Stable sorts preserve the relative order of equal elements.

Use cases

Database ORDER BY
Preprocessing before search
Rankings and leaderboards
Deduplication (sort + adjacent comparison)

Examples

Input
```
[3,1,4,1,5] → quicksort
```
Output
```
[1,1,3,4,5]
```
O(n log n) average

Common errors

Quicksort recursion overhead is high for small arrays: Use insertion sort for small arrays (a quicksort optimization)

Related terms

Big O notation describes the asymptotic upper bound of a function, used to analyze algorithm time/space complexity while ignoring constants and lower-order terms.

Binary search compares against the middle of a sorted array and halves the range each time, locating a target in O(log n); it is the foundational efficient search algorithm.

A hash table maps keys to a bucket array via a hash function, providing average O(1) lookup/insert/delete; it is among the most used data structures.

Related tools

Sort lines alphabetically, numerically, by length, or naturally; deduplicate; reverse or shuffle. Free, private, and 100% client-side.

References