# partial_sort

 Category: algorithms Component type: function

## Prototype

`Partial_sort` is an overloaded name; there are actually two `partial_sort` functions.

```template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
```

## Description

`Partial_sort` rearranges the elements in the range `[first, last)` so that they are partially in ascending order. Specifically, it places the smallest `middle - first` elements, sorted in ascending order, into the range `[first, middle)`. The remaining `last - middle` elements are placed, in an unspecified order, into the range `[middle, last)`. [1] [2]

The two versions of `partial_sort` differ in how they define whether one element is less than another. The first version compares objects using `operator<`, and the second compares objects using a functors `comp`.

The postcondition for the first version of `partial_sort` is as follows. If `i` and `j` are any two valid iterators in the range `[first, middle)` such that `i` precedes `j`, and if `k` is a valid iterator in the range `[middle, last)`, then `*j < *i` and `*k < *i` will both be `false`. The corresponding postcondition for the second version of `partial_sort` is that `comp(*j, *i)` and `comp(*k, *i)` are both false. Informally, this postcondition means that the first `middle - first` elements are in ascending order and that none of the elements in `[middle, last)` is less than any of the elements in `[first, middle)`.

## Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

## Requirements on types

For the first version:

• `RandomAccessIterator` is a model of RandomAccessIterator.
• `RandomAccessIterator` is mutable.
• `RandomAccessIterator`'s value type is LessThanComparable.
• The ordering relation on `RandomAccessIterator`'s value type is a strict weak ordering, as defined in the LessThanComparable requirements.

For the second version:

• `RandomAccessIterator` is a model of RandomAccessIterator.
• `RandomAccessIterator` is mutable.
• `StrictWeakOrdering` is a model of StrictWeakOrdering.
• `RandomAccessIterator`'s value type is convertible to `StrictWeakOrdering`'s argument type.

## Preconditions

• `[first, middle)` is a valid range.
• `[middle, last)` is a valid range.

(It follows from these two conditions that `[first, last)` is a valid range.)

## Complexity

Approximately `(last - first) * log(middle - first)` comparisons.

## Example

```int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

partial_sort(A, A + 5, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4 5 11 12 10 9 8 7 6".
```

## Notes

[1] Note that the elements in the range `[first, middle)` will be the same (ignoring, for the moment, equivalent elements) as if you had sorted the entire range using `sort(first, last)`. The reason for using `partial_sort` in preference to `sort` is simply efficiency: a partial sort, in general, takes less time.

[2] `partial_sort(first, last, last)` has the effect of sorting the entire range `[first, last)`, just like `sort(first, last)`. They use different algorithms, however: `sort` uses the introsort algorithm (a variant of quicksort), and `partial_sort` uses heapsort. See section 5.2.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.), and J. W. J. Williams (CACM 7, 347, 1964). Both heapsort and introsort have complexity of order `N log(N)`, but introsort is usually faster by a factor of 2 to 5.

`partial_sort_copy`, `sort`, `stable_sort`, `binary_search`, `lower_bound`, `upper_bound`, `less<T>`, StrictWeakOrdering, LessThanComparable