Introduction to Sorting
This page briefly introduces sorting algorithms.
Definition
A sorting algorithm is an algorithm that arranges a given collection of data in some order. There are many sorting algorithms, and most of them differ in their properties.
Properties
Stability
Stability is about whether sorting changes the relative order of equal elements.
A stable algorithm keeps records with equal keys in their original relative order. That is, if a sorting algorithm is stable and two records \(R\) and \(S\) have equal keys, with \(R\) before \(S\) in the original list, then \(R\) is also before \(S\) in the sorted list.
Radix sort, counting sort, insertion sort, bubble sort and merge sort are stable sorts.
Selection sort, heapsort, quicksort and Shellsort are not stable sorts.
Time complexity
Main page: Complexity
Time complexity measures how an algorithm's running time depends on its input size. It is usually written with \(O\).
A simple way to work out a complexity is to count the number of times "simple operations" are executed. Sometimes you can get a rough estimate just by counting how deeply the loops are nested.
An algorithm has a best-case time complexity, an average-case time complexity and a worst-case time complexity. In OI contests you usually care about the worst case, because it is a lower bound on how well the algorithm performs: nothing worse can happen during judging.
Any comparison-based algorithm that sorts \(n\) arbitrary distinct elements needs \(\Omega(n\log n)\) comparisons in the worst case.
Of course, not every sorting algorithm is \(O(n\log n)\). For example, counting sort runs in \(O(n+w)\), where \(w\) is the size of the value range of the input.
The following compares several sorting algorithms.
Space complexity
Like time complexity, space complexity describes how much space an algorithm uses. In general, the lower the space complexity, the better the algorithm.
External links
- Sorting algorithm - Wikipedia, the free encyclopedia (in Chinese)
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, ouuan, NachtgeistW, Enter-tainer, Great-designer, Backl1ght, Alisahhh, Junyan721113, iamtwz, zirnc, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.