Practice Now
C++ sorting
index tracking
std::sort
duplicate question
algorithms

c sort keeping track of indices

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsC & C++

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:

cpp
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:

cpp
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:

cpp
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:

cpp
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:

cpp
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:

cpp
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
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.