Introduction
When sorting an array in C++, you sometimes need to know the original positions of elements after sorting. The standard std::sort rearranges elements in-place and discards positional information. To track original indices, you sort an array of indices based on the values they reference, or sort pairs of (value, index).
Method 1: Sort an Index Array
Create a separate index array and sort it using the values as comparison keys:
1#include <algorithm>
2#include <vector>
3#include <numeric>
4#include <iostream>
5
6int main() {
7 std::vector<int> values = {40, 10, 30, 20, 50};
8
9 // Create index array [0, 1, 2, 3, 4]
10 std::vector<int> indices(values.size());
11 std::iota(indices.begin(), indices.end(), 0);
12
13 // Sort indices based on values
14 std::sort(indices.begin(), indices.end(),
15 [&values](int a, int b) {
16 return values[a] < values[b];
17 });
18
19 // indices = [1, 3, 2, 0, 4]
20 // meaning: smallest is values[1]=10, next is values[3]=20, etc.
21 for (int i : indices) {
22 std::cout << "index=" << i << " value=" << values[i] << "\n";
23 }
24 // index=1 value=10
25 // index=3 value=20
26 // index=2 value=30
27 // index=0 value=40
28 // index=4 value=50
29
30 return 0;
31}
This is the most common and efficient approach — the original array remains unchanged.
Method 2: Sort Pairs of (Value, Index)
Pack each value with its original index, then sort the pairs:
1#include <algorithm>
2#include <vector>
3#include <iostream>
4
5int main() {
6 std::vector<int> values = {40, 10, 30, 20, 50};
7
8 // Create pairs of (value, original_index)
9 std::vector<std::pair<int, int>> indexed;
10 for (int i = 0; i < values.size(); i++) {
11 indexed.emplace_back(values[i], i);
12 }
13
14 // Sort by value
15 std::sort(indexed.begin(), indexed.end());
16
17 for (const auto& [val, idx] : indexed) {
18 std::cout << "value=" << val << " original_index=" << idx << "\n";
19 }
20 // value=10 original_index=1
21 // value=20 original_index=3
22 // value=30 original_index=2
23 // value=40 original_index=0
24 // value=50 original_index=4
25
26 return 0;
27}
Method 3: Using a Struct
For complex data where you want to track multiple fields:
1struct Element {
2 int value;
3 int originalIndex;
4};
5
6std::vector<int> values = {40, 10, 30, 20, 50};
7std::vector<Element> elements;
8
9for (int i = 0; i < values.size(); i++) {
10 elements.push_back({values[i], i});
11}
12
13std::sort(elements.begin(), elements.end(),
14 [](const Element& a, const Element& b) {
15 return a.value < a.value; // ascending by value
16 });
Method 4: Using std::stable_sort
If you need to preserve the relative order of equal elements:
1std::vector<int> values = {30, 10, 30, 20, 10};
2
3std::vector<int> indices(values.size());
4std::iota(indices.begin(), indices.end(), 0);
5
6// stable_sort preserves relative order of equal elements
7std::stable_sort(indices.begin(), indices.end(),
8 [&values](int a, int b) {
9 return values[a] < values[b];
10 });
11
12// indices = [1, 4, 3, 0, 2]
13// The two 10s (indices 1,4) keep their relative order
14// The two 30s (indices 0,2) keep their relative order
Getting the Rank of Each Element
Sometimes you need the inverse mapping — for each element, what is its rank after sorting:
1std::vector<int> values = {40, 10, 30, 20, 50};
2
3// Step 1: sort indices
4std::vector<int> indices(values.size());
5std::iota(indices.begin(), indices.end(), 0);
6std::sort(indices.begin(), indices.end(),
7 [&values](int a, int b) { return values[a] < values[b]; });
8
9// Step 2: invert to get ranks
10std::vector<int> ranks(values.size());
11for (int i = 0; i < indices.size(); i++) {
12 ranks[indices[i]] = i;
13}
14
15// ranks = [3, 0, 2, 1, 4]
16// values[0]=40 has rank 3, values[1]=10 has rank 0, etc.
Practical Example: Top-K Elements
Find the indices of the k largest elements:
1std::vector<double> scores = {0.8, 0.2, 0.95, 0.1, 0.7};
2
3std::vector<int> indices(scores.size());
4std::iota(indices.begin(), indices.end(), 0);
5
6// Partial sort: find top 3
7std::partial_sort(indices.begin(), indices.begin() + 3, indices.end(),
8 [&scores](int a, int b) {
9 return scores[a] > scores[b]; // descending
10 });
11
12std::cout << "Top 3 indices: ";
13for (int i = 0; i < 3; i++) {
14 std::cout << indices[i] << " "; // 2 0 4
15}
Common Pitfalls
Space Complexity: The additional space required is O(n) due to the need to store the indices or pairs.
Stability: std::sort is not guaranteed to be stable. Use std::stable_sort if you need equal elements to preserve their original relative order.
Avoiding Too Much Copying: If the element type is expensive to copy, sort an index array (Method 1) rather than pairs. The index array only moves integers.
Lambda capture: When sorting indices with a lambda, capture the values array by reference ([&values]), not by value, to avoid copying the entire array.
Integer overflow: When computing ranks or using indices as offsets, ensure your index type can hold the array size. Use size_t or int64_t for very large arrays.
Summary
Sort an index array with a custom comparator referencing the original values (most common)
Use std::iota to initialize index arrays: [0, 1, 2, ..., n-1]
Use std::stable_sort when equal elements must preserve their original order
Invert the sorted index array to get per-element ranks
For top-K problems, use std::partial_sort for better performance than full sorting
