# partial_sort_copy

 Category: algorithms Component type: function

## Prototype

`Partial_sort_copy` is an overloaded name; there are actually two `partial_sort_copy` functions.

```template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator,
class StrictWeakOrdering>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
```

## Description

`Partial_sort_copy` copies the smallest `N` elements from the range `[first, last)` to the range `[result_first, result_first + N)`, where `N` is the smaller of `last - first` and `result_last - result_first`. The elements in `[result_first, result_first + N)` will be in ascending order.

The two versions of `partial_sort_copy` 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_copy` is as follows. If `i` and `j` are any two valid iterators in the range `[result_first, result_first + N)` such that `i` precedes `j`, then `*j < *i` will be `false`. The corresponding postcondition for the second version is that `comp(*j, *i)` will be `false`.

The return value is `result_first + N`.

## Definition

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

## Requirements on types

For the first version:

• `InputIterator` is a model of InputIterator.
• `RandomAccessIterator` is a model of RandomAccessIterator.
• `RandomAccessIterator` is mutable.
• The value types of `InputIterator` and `RandomAccessIterator` are the same.
• `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:

• `InputIterator` is a model of InputIterator.
• `RandomAccessIterator` is a model of RandomAccessIterator.
• `RandomAccessIterator` is mutable.
• The value types of `InputIterator` and `RandomAccessIterator` are the same.
• `StrictWeakOrdering` is a model of StrictWeakOrdering.
• `RandomAccessIterator`'s value type is convertible to `StrictWeakOrdering`'s argument type.

## Preconditions

• `[first, last)` is a valid range.
• `[result_first, result_last)` is a valid range.
• `[first, last)` and `[result_first, result_last)` do not overlap.

## Complexity

Approximately `(last - first) * log(N)` comparisons, where `N` is the smaller of `last - first` and `result_last - result_first`.

## Example

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

vector<int> V(4);
partial_sort_copy(A, A + N, V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4".
```

## Notes

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