Skip to content
Quantoros

Walk through std::sort, std::stablesort, std::partialsort, and std::nthelement — when would you pick each?

C++Level: IntermediateSTL Containers & Iterators

Walk through std::sort, std::stable_sort, std::partial_sort, and std::nth_element — when would you pick each?

Hints
  • Identify types, object lifetimes and compile-time decisions.
  • Separate language guarantees from a particular compiler's behavior.

Answer

Sorting

std::sort

:Source: src/algorithm/sort

std::sort rearranges elements in ascending order by default using an introsort algorithm (a hybrid of quicksort, heapsort, and insertion sort) that guarantees O(n log n) worst-case complexity. The algorithm requires random access iterators, so it works with std::vector, std::array, and std::deque, but not with std::list (use list.sort() instead). For custom ordering, provide a comparison function or use std::greater<> for descending order. Note that std::sort is not stable—equal elements may be reordered relative to their original positions.

#include <algorithm>
#include <vector>

int main() {
  std::vector v{3, 1, 4, 1, 5, 9, 2, 6};

  std::sort(v.begin(), v.end());  // ascending
  std::sort(v.begin(), v.end(), std::greater<>{});  // descending

  // custom comparator
  std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
}

std::stable_sort

:Source: src/algorithm/stable-sort

std::stable_sort preserves the relative order of elements that compare equal, which is essential when sorting by multiple criteria sequentially. For example, if you first sort employees by name and then by department, employees within the same department will remain sorted by name. The algorithm uses merge sort and guarantees O(n log n) complexity when sufficient memory is available, or O(n log² n) otherwise. Use std::stable_sort when the original ordering of equivalent elements carries semantic meaning.

#include <algorithm>
#include <vector>

struct Item {
  int priority;
  int order;
};

int main() {
  std::vector<Item> items{{1, 1}, {2, 2}, {1, 3}, {2, 4}};

  // stable_sort preserves original order for equal elements
  std::stable_sort(items.begin(), items.end(),
                   [](auto &a, auto &b) { return a.priority < b.priority; });
  // items with same priority keep their original relative order
}

std::partial_sort

:Source: src/algorithm/partial-sort

std::partial_sort sorts only the first N elements of a range, leaving the remaining elements in an unspecified order. This is significantly more efficient than a full sort when you only need the top N results—it runs in O(n log k) time where k is the number of elements to sort, compared to O(n log n) for a full sort. Common use cases include finding the top 10 scores, the 5 smallest values, or implementing pagination where only the first page needs to be sorted.

#include <algorithm>
#include <vector>

int main() {
  std::vector v{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

  // sort only first 3 elements
  std::partial_sort(v.begin(), v.begin() + 3, v.end());
  // v: {0, 1, 2, ...} first 3 are sorted, rest unspecified
}

std::nth_element

:Source: src/algorithm/nth-element

std::nth_element is a selection algorithm that partially sorts a range so that the element at the nth position is exactly the element that would be there if the range were fully sorted. All elements before the nth are less than or equal to it, and all elements after are greater than or equal. This runs in O(n) average time, making it ideal for finding medians, percentiles, or partitioning data around a pivot value without the overhead of a full sort.

#include <algorithm>
#include <vector>

int main() {
  std::vector v{5, 6, 4, 3, 2, 6, 7, 9, 3};

  // find median (middle element)
  auto mid = v.begin() + v.size() / 2;
  std::nth_element(v.begin(), mid, v.end());
  // *mid is now the median value
}

Answer section

Source and licence: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT

Related questions