Pointer Sort
When records are big, don't move them. Sort an array of pointers (or indices) to the records instead, and only small addresses get swapped.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A library has 10,000 heavy books on shelves. To list them by title you don’t carry the books around. You sort the index cards that say where each book is. The books never move; the cards do.
That is pointer sort (also called indirect or index sort).
The problem it solves
Each swap in a normal sort copies whole items. If each item is a big struct (name, ID, address, photo…), every swap copies hundreds of bytes three times. That’s slow.
The trick
- Make an array of pointers:
p[i] = &records[i]. - Run any sort on p, but compare through the pointers:
p[j]->score < p[min]->score. - Swap pointers:
swap(p[i], p[min]). Each swap moves 8 bytes. - Read records in order through p:
p[0]->name,p[1]->name, …
The original array keeps its order. You can even keep several pointer arrays (by name, by score, by ID) over the same data at once.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
The "records" row never changes. Only the p[ ] row moves.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <string>
#include <utility>
using namespace std;
struct Student {
string name;
int score;
char bigData[1000]; // pretend each record is large and slow to copy
};
// Sort an array of POINTERS by score. The records never move.
void pointerSort(Student* p[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (p[j]->score < p[min]->score)
min = j;
swap(p[i], p[min]); // swaps two addresses (8 bytes), not two records
}
}
int main() {
Student s[5] = {{"Abel", 72, {}}, {"Bethel", 95, {}}, {"Dawit", 58, {}},
{"Hana", 81, {}}, {"Kidus", 66, {}}};
const int n = 5;
Student* p[n];
for (int i = 0; i < n; i++) p[i] = &s[i];
pointerSort(p, n);
cout << "Sorted view: ";
for (int i = 0; i < n; i++) cout << p[i]->name << "(" << p[i]->score << ") ";
cout << "\nOriginal array: ";
for (int i = 0; i < n; i++) cout << s[i].name << " ";
cout << "\n";
}Sorted view: Dawit(58) Kidus(66) Abel(72) Hana(81) Bethel(95) Original array: Abel Bethel Dawit Hana Kidus
05Complexity
| Comparisons | same as the underlying sort (here selection: n(n−1)/2) |
|---|---|
| Data moved per swap | one pointer (8 bytes) instead of one whole record |
| Time | O(n²) with selection sort; O(n log n) with a fast sort |
| Extra space | O(n) for the pointer array |
| Stable? | No |
| In-place? | No |
Pointer sort is a technique, not a new algorithm. Any sort (selection, insertion, quick…) can be made indirect.
06Watch
Introduction to pointers in C/C++
Why this one: You need pointers for this; mycodeschool's intro is the best 10-minute refresher.
Selection sort algorithm
Why this one: The underlying sort in our example is selection sort.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- What is pointer sort and why is it used?
- Write a function that sorts an array of pointers to
Studentrecords by score. - After pointer-sorting, how do you print records in sorted order? Has the original array changed?
- Compare the cost of a swap in normal sorting vs pointer sorting for 1 KB records.
Common mistakes
- Swapping the records (
swap(*p[i], *p[min])) instead of the pointers (swap(p[i], p[min])). That defeats the purpose. - Comparing the pointers themselves (
p[j] < p[min]) instead of what they point to (p[j]->score). - Forgetting to initialise
p[i] = &s[i]before sorting.
08Quick check
09Practice
🟢 Trace by hand
Records: [0] Abel 72, [1] Bethel 95, [2] Dawit 58. Show p[] (as indices) after each pass of pointer selection sort by score.
Show answer
- Start:
p = [0, 1, 2] - Pass 1: min score 58 at p[2] → swap p[0], p[2] →
p = [2, 1, 0] - Pass 2: compare Bethel 95 vs Abel 72 → swap →
p = [2, 0, 1]
Sorted order: Dawit, Abel, Bethel. The records array is untouched.
🟡 Implement it
Rewrite pointer sort using an int idx[] array of indices instead of pointers, and sort by name alphabetically.
Hint
Compare s[idx[j]].name < s[idx[min]].name, swap idx[i] and idx[min].
Solution
void indexSort(Student s[], int idx[], int n) {
for (int i = 0; i < n; i++) idx[i] = i;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (s[idx[j]].name < s[idx[min]].name) min = j;
swap(idx[i], idx[min]);
}
}🔴 Solve problems
Hint
Exactly pointer/index sort. Sort an index array by
heights[i](descending), then outputnames[idx[k]].Hint
Sort indices by value, then walk them to assign ranks without disturbing the original order.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.