Editing Order statistic (section)

== Computing order statistics ==
{{main|Selection algorithm|Sampling in order}}

The problem of computing the ''k''th smallest (or largest) element of a list is called the selection problem and is solved by a selection algorithm. Although this problem is difficult for very large lists, sophisticated selection algorithms have been created that can solve this problem in time proportional to the number of elements in the list, even if the list is totally unordered. If the data is stored in certain specialized data structures, this time can be brought down to O(log ''n''). In many applications all order statistics are required, in which case a [[sorting algorithm]] can be used and the time taken is  O(''n'' log ''n'').