# 3.4 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.

Chapter: Simple Sorting & Searching · ~30 min · medium
URL: https://dsa.fetehadin.com/learn/pointer-sort

## Mental 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

1. Make an array of pointers: `p[i] = &records[i]`.
2. Run any sort on **p**, but compare through the pointers: `p[j]->score < p[min]->score`.
3. Swap **pointers**: `swap(p[i], p[min])`. Each swap moves 8 bytes.
4. 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.

## C++ code: pointer-sort.cpp

```cpp
#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";
}
```

Expected output:

```text
Sorted view:   Dawit(58) Kidus(66) Abel(72) Hana(81) Bethel(95) 
Original array: Abel Bethel Dawit Hana Kidus
```

## Complexity

| Case | Cost |
| --- | --- |
| 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 |

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.

## Videos

- [Introduction to pointers in C/C++](https://youtu.be/h-HBipu_1P0) (mycodeschool): You need pointers for this; mycodeschool's intro is the best 10-minute refresher.
- [Selection sort algorithm](https://youtu.be/GUDLRan2DWM) (mycodeschool): The underlying sort in our example is selection sort.

## Exam lens

Likely questions:

- What is pointer sort and why is it used?
- Write a function that sorts an array of pointers to `Student` records 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.

## Quick check

1. In pointer sort, what gets swapped?
   A. The records
   B. The pointers (or indices) to the records
   C. The keys only
   D. Nothing
   Answer: B. Records stay put; only small addresses move.

2. Which line correctly compares scores through pointers?
   A. `if (p[j] < p[min])`
   B. `if (p[j]->score < p[min]->score)`
   C. `if (*p[j] < *p[min])`
   D. `if (&p[j] < &p[min])`
   Answer: B. `->` follows the pointer to the struct and reads its `score`.

3. After pointer sort, the original `Student s[]` array is…
   A. sorted
   B. unchanged
   C. reversed
   D. deleted
   Answer: B. Only the pointer array p[] is in sorted order.

4. Main benefit of pointer sort?
   A. Fewer comparisons
   B. Less data copied per swap
   C. O(n log n) time
   D. No extra memory
   Answer: B. Comparisons are the same; the saving is in how much data each swap moves.

## Practice

**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.

Solution:

- 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]`.

```cpp
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]);
    }
}
```


**Problems:**

- [Sort the People](https://leetcode.com/problems/sort-the-people/) (easy). Hint: Exactly pointer/index sort. Sort an index array by `heights[i]` (descending), then output `names[idx[k]]`.
- [Rank Transform of an Array](https://leetcode.com/problems/rank-transform-of-an-array/) (easy). Hint: Sort indices by value, then walk them to assign ranks without disturbing the original order.

## Mastery checklist

- [ ] I can explain why we sort pointers instead of records.
- [ ] I can write pointer sort with `->` comparisons and pointer swaps.
- [ ] I can print records in sorted order through the pointer array.
- [ ] I can do the same with an index array.