# 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 function object `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 Random Access Iterator.
- `RandomAccessIterator` is mutable.
- `RandomAccessIterator`'s value type is LessThan Comparable.
- The ordering relation on `RandomAccessIterator`'s value type is a strict weak ordering, as defined in the LessThan Comparable requirements.

For the second version:

- `RandomAccessIterator` is a model of Random Access Iterator.
- `RandomAccessIterator` is mutable.
- `StrictWeakOrdering` is a model of Strict Weak Ordering.
- `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.

### See also

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

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation