Sorting Stability and When to Use Which Sort in DSA C++

Mental Model

Stable sorting keeps equal items in the same order they started. Different sorts work best for different situations.

Analogy: Imagine sorting playing cards by number but keeping the order of cards with the same number as they were originally dealt.

Unsorted list:
5a -> 3 -> 5b -> 2 -> 3 -> null

Stable sort keeps 5a before 5b and the first 3 before the second 3.

Dry Run Walkthrough

Input: list: 5a -> 3 -> 5b -> 2 -> 3, stable sort by number ascending

Goal: Sort the list by number ascending while keeping the order of equal numbers the same

Step 1: compare 5a and 3, 3 is smaller so move 3 before 5a

3 -> 5a -> 5b -> 2 -> 3 -> null

Why: We want smaller numbers first

Step 2: compare 5a and 5b, both 5 so keep 5a before 5b

3 -> 5a -> 5b -> 2 -> 3 -> null

Why: Stable sort keeps original order of equal elements

Step 3: compare 5b and 2, 2 is smaller so move 2 before 5b

3 -> 5a -> 2 -> 5b -> 3 -> null

Why: Smaller number 2 should come before 5b

Step 4: compare 3 and 2, 2 is smaller so move 2 before 3

2 -> 3 -> 5a -> 5b -> 3 -> null

Why: 2 is smallest so it goes first

Step 5: compare last 3 with previous 3, keep order same

2 -> 3 -> 3 -> 5a -> 5b -> null

Why: Stable sort keeps equal elements in original order

Result:

2 -> 3 -> 3 -> 5a -> 5b -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

struct Card {
    int number;
    char id; // to distinguish duplicates
};

// Stable insertion sort for demonstration
void stableInsertionSort(std::vector<Card>& cards) {
    for (int i = 1; i < (int)cards.size(); i++) {
        Card key = cards[i];
        int j = i - 1;
        // Move elements greater than key.number one position ahead
        while (j >= 0 && cards[j].number > key.number) {
            cards[j + 1] = cards[j];
            j--;
        }
        cards[j + 1] = key; // Insert key at correct position
    }
}

void printCards(const std::vector<Card>& cards) {
    for (const auto& c : cards) {
        std::cout << c.number << c.id << " -> ";
    }
    std::cout << "null" << std::endl;
}

int main() {
    std::vector<Card> cards = {{5, 'a'}, {3, ' '}, {5, 'b'}, {2, ' '}, {3, ' '}};
    std::cout << "Before sorting:" << std::endl;
    printCards(cards);
    stableInsertionSort(cards);
    std::cout << "After stable sorting by number ascending:" << std::endl;
    printCards(cards);
    return 0;
}

for (int i = 1; i < (int)cards.size(); i++) {

iterate over cards starting from second element

while (j >= 0 && cards[j].number > key.number) {

shift cards greater than key to the right

cards[j + 1] = key;

insert key at correct sorted position

Output

Before sorting:

5a -> 3  -> 5b -> 2  -> 3  -> null

After stable sorting by number ascending:

2  -> 3  -> 3  -> 5a -> 5b -> null

Complexity Analysis

Time: O(n^2) because insertion sort compares and shifts elements in worst case

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Stable sorts like insertion or merge keep order of equal elements, unlike quicksort which is usually unstable but faster O(n log n)

Edge Cases

empty list

no sorting needed, list remains empty

DSA C++

for (int i = 1; i < (int)cards.size(); i++) {

list with all equal elements

order remains same because stable sort preserves order

DSA C++

while (j >= 0 && cards[j].number > key.number) {

list with one element

no sorting needed, list remains same

DSA C++

for (int i = 1; i < (int)cards.size(); i++) {

When to Use This Pattern

When you need to keep the original order of equal elements after sorting, look for a stable sort like insertion or merge sort.

Common Mistakes

Mistake: Using an unstable sort when order of equal elements matters
Fix: Choose a stable sorting algorithm or modify the sort to preserve order

Mistake: Assuming all sorts are stable by default
Fix: Check the algorithm's stability property before using it

Summary

Stable sorting keeps equal elements in their original order after sorting.

Use stable sorts when the order of equal items matters, like sorting cards or records with multiple keys.

The key insight is that stable sorts never reorder equal elements, preserving their initial sequence.

Practice

1. Which of the following sorting algorithms is stable by default?

easy

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. Selection Sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of equal elements the same as in the input.

2. Step 2: Check common sorting algorithms

   Merge Sort is stable because it merges sorted halves without changing order of equal elements. Quick Sort, Heap Sort, and Selection Sort are not stable by default.

3. Final Answer:

   Merge Sort -> Option A

4. Quick Check:

   Stable sort = Merge Sort [OK]

Hint: Remember: Merge Sort is stable, Quick Sort is not [OK]

Common Mistakes:

• Thinking Quick Sort is stable
• Confusing stability with time complexity
• Assuming all comparison sorts are stable

2. Which syntax correctly declares a stable sort call on a vector v in C++ STL?

easy

A. v.stable_sort();

B. std::sort(v.begin(), v.end(), stable);

C. std::stable_sort(v.begin(), v.end());

D. std::sort_stable(v.begin(), v.end());

Solution

1. Step 1: Recall C++ STL stable sort syntax

   The function is std::stable_sort with two iterators as arguments.

2. Step 2: Check options for correctness

   std::stable_sort(v.begin(), v.end()); matches correct syntax. Options A, B, and D are invalid or do not exist in STL.

3. Final Answer:

   std::stable_sort(v.begin(), v.end()); -> Option C

4. Quick Check:

   Correct stable sort syntax = std::stable_sort(v.begin(), v.end()); [OK]

Hint: Use std::stable_sort with iterators for stable sorting [OK]

Common Mistakes:

• Using std::sort for stable sorting
• Calling non-existent member functions
• Passing wrong arguments to sort functions

3. What is the output of the following C++ code snippet?

struct Item {
  int key;
  char id;
};

std::vector<Item> v = {{2, 'a'}, {1, 'b'}, {2, 'c'}};
std::stable_sort(v.begin(), v.end(), [](Item x, Item y) { return x.key < y.key; });
for (auto &item : v) std::cout << item.key << item.id << ' ';

medium

A. 2c 2a 1b

B. 1b 2c 2a

C. 2a 2c 1b

D. 1b 2a 2c

Solution

1. Step 1: Understand stable_sort behavior

   stable_sort sorts by key ascending but keeps relative order of equal keys.

2. Step 2: Sort vector and trace output

   Keys sorted: 1, 2, 2. For key=2, 'a' comes before 'c' in original, so order stays '2a' then '2c'. Output: "1b 2a 2c "

3. Final Answer:

   1b 2a 2c -> Option D

4. Quick Check:

   Stable sort keeps order of equal keys [OK]

Hint: Stable sort keeps original order for equal keys [OK]

Common Mistakes:

• Assuming equal keys reorder arbitrarily
• Confusing stable_sort with sort
• Ignoring the lambda comparator effect

4. Identify the error in this code snippet that tries to use stable sort on an array:

int arr[] = {3, 1, 2};
std::stable_sort(arr, arr + 3);
for (int i = 0; i < 3; i++) std::cout << arr[i] << ' ';

medium

A. No error; code runs correctly

B. Array pointers used incorrectly in stable_sort

C. stable_sort cannot be used on arrays

D. Missing comparator function causes error

Solution

1. Step 1: Check stable_sort usage on arrays

   std::stable_sort accepts pointers as iterators, so arr and arr+3 are valid.

2. Step 2: Verify code correctness

   Code sorts array {3,1,2} to {1,2,3} and prints correctly. No error present.

3. Final Answer:

   No error; code runs correctly -> Option A

4. Quick Check:

   stable_sort works with array pointers [OK]

Hint: stable_sort works with pointers, no comparator needed for default order [OK]

Common Mistakes:

• Thinking stable_sort needs vector only
• Assuming comparator is mandatory
• Confusing pointers with iterators

5. You have a list of employees with fields name and age. You want to sort them by age but keep the original order for employees with the same age. Which sorting algorithm should you use and why?

hard

A. Heap Sort, because it uses less memory

B. Stable Sort (like Merge Sort), to preserve order of equal ages

C. Quick Sort, because it is faster on average

D. Selection Sort, because it is simple to implement

Solution

1. Step 1: Understand requirement for stability

   We want to keep original order for employees with same age, so sorting must be stable.

2. Step 2: Choose sorting algorithm based on stability

   Merge Sort or any stable sort preserves order of equal keys. Quick Sort, Heap Sort, Selection Sort are not stable by default.

3. Final Answer:

   Stable Sort (like Merge Sort), to preserve order of equal ages -> Option B

4. Quick Check:

   Stable sort needed to keep order [OK]

Hint: Use stable sort to keep order of equal keys [OK]

Common Mistakes:

• Choosing faster but unstable sorts
• Ignoring stability requirement
• Confusing simplicity with correctness