Applications of Sorting
This page gives a brief introduction to the applications of sorting.
Understanding the data
Sorting data helps us understand its characteristics and makes later analysis and visualization easier. Take everyday examples such as dictionaries and menus: if they were not arranged in some order, finding what you need would take far longer.
Computers have to process data on a large scale. Once the data is sorted, we can design the computer's subsequent processing around the characteristics of the data and our needs.
Reducing time complexity
Sorting as a preprocessing step can lower the time complexity of solving a problem; usually this is a matter of trading space for time. If a sorted list is going to be analyzed many times, paying the cost of sorting just once is a good deal, because every later analysis becomes much faster.
Example: checking whether a given sequence contains equal elements
You are given a sequence of numbers and have to check whether any of its elements are equal.
A naive approach is to check every pair of numbers and test whether the two are equal. This takes \(O(n^2)\) time.
Instead, sort the numbers first. If two numbers are equal, they must be adjacent in the new sequence, so all that remains is one \(O(n)\) scan of it.
The total time complexity is that of the sort, \(O(n\log n)\).
Preprocessing for search
Sorting is the preprocessing that binary search requires. Once the sequence is sorted, binary search finds a given element in it in \(O(\log n)\) time.
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, sshwy, NachtgeistW, leoleoasd, Enter-tainer, Persdre, 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.