In [[computer science]], '''partial sorting''' is a [[Relaxation (approximation)|relaxed]] variant of the [[Sorting algorithm|sorting]] problem. IfTotal sorting is the problem of [[permutation|permuting]]returning a list of items such that its elements all appear in order, thenwhile partial sorting amountsis to findingreturning a permutationlist suchof thatthe some''k'' predeterminedsmallest set(or of''k'' indexeslargest) appearelements in theorder. positionThe ofother elements (above the permutation''k'' thatsmallest theyones) wouldmay havealso inbe thestored, sortedas in permutation;an in-place otherpartial wordssort, foror eachmay requestedbe index ''i''discarded, elementwhich ''i''is common in streaming partial sorts. A common practical example of partial sorting is computing the partially"Top sorted100" of some list. containsA [[orderfurther statistic]]relaxation only requires returning a list of the ''ik'' ofsmallest elements, but without requiring that these be ordered. This latter form is quite close to the input[[selection listalgorithm|selection]] problem.
In terms of indices, in a partially sorted list, for every index ''i'' from 1 to ''k,'' the ''i''th element is in the same place as it would be in the fully sorted list: element ''i'' of the partially sorted list contains [[order statistic]] ''i'' of the input list.
