Sorting Stability and When to Use Which Sort in DSA Java

Mental Model

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

Analogy: Imagine sorting a deck of playing cards by number but keeping the order of suits the same if numbers match, like stacking books by height but keeping the same color order for books of the same height.

Unsorted list:
[5♠] -> [3♦] -> [5♥] -> [2♣] -> [3♠] -> null

Stable sort result (by number):
[2♣] -> [3♦] -> [3♠] -> [5♠] -> [5♥] -> null

Unstable sort result (by number):
[2♣] -> [3♠] -> [3♦] -> [5♥] -> [5♠] -> null

Dry Run Walkthrough

Input: list: 5♠ -> 3♦ -> 5♥ -> 2♣ -> 3♠, sort by number ascending

Goal: Sort the list by number while keeping the original order of equal numbers (stable sort)

Step 1: Compare first two nodes 5♠ and 3♦, 3 < 5 so swap

[3♦] -> [5♠] -> [5♥] -> [2♣] -> [3♠] -> null

Why: Smaller number should come first to start sorting

Step 2: Compare 5♠ and 5♥, numbers equal so keep order (stable)

[3♦] -> [5♠] -> [5♥] -> [2♣] -> [3♠] -> null

Why: Stable sort keeps original order of equal elements

Step 3: Compare 5♥ and 2♣, 2 < 5 so swap

[3♦] -> [5♠] -> [2♣] -> [5♥] -> [3♠] -> null

Why: Smaller number moves forward to correct position

Step 4: Compare 5♥ and 3♠, 3 < 5 so swap

[3♦] -> [5♠] -> [2♣] -> [3♠] -> [5♥] -> null

Why: Smaller number moves forward to correct position

Step 5: Repeat passes until fully sorted and stable order kept

[2♣] -> [3♦] -> [3♠] -> [5♠] -> [5♥] -> null

Why: Final sorted list with stable order of equal numbers

Result:

[2♣] -> [3♦] -> [3♠] -> [5♠] -> [5♥] -> null

Annotated Code

DSA Java

import java.util.*;

class Card {
    int number;
    char suit;
    Card(int number, char suit) {
        this.number = number;
        this.suit = suit;
    }
    public String toString() {
        return number + "" + suit;
    }
}

public class StableSortDemo {

    // Stable sort using insertion sort
    public static void stableSort(List<Card> cards) {
        for (int i = 1; i < cards.size(); i++) {
            Card key = cards.get(i);
            int j = i - 1;
            // Move elements greater than key one position ahead
            while (j >= 0 && cards.get(j).number > key.number) {
                cards.set(j + 1, cards.get(j)); // shift right
                j--;
            }
            cards.set(j + 1, key); // insert key
        }
    }

    // Unstable sort using selection sort picking rightmost min
    public static void unstableSort(List<Card> cards) {
        for(int i = 0; i < cards.size() - 1; i++) {
            int minIdx = i;
            for(int j = i + 1; j < cards.size(); j++) {
                if(cards.get(j).number < cards.get(minIdx).number) {
                    minIdx = j;
                }
            }
            Collections.swap(cards, i, minIdx);
        }
    }

    public static void printList(List<Card> cards) {
        for (Card c : cards) {
            System.out.print(c + " -> ");
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        List<Card> cards1 = new ArrayList<>();
        cards1.add(new Card(5, '\u2660'));// ♠
        cards1.add(new Card(3, '\u2666'));// ♦
        cards1.add(new Card(5, '\u2665'));// ♥
        cards1.add(new Card(2, '\u2663'));// ♣
        cards1.add(new Card(3, '\u2660'));// ♠

        System.out.println("Original list:");
        printList(cards1);

        stableSort(cards1);
        System.out.println("After stable sort by number:");
        printList(cards1);

        List<Card> cards2 = new ArrayList<>();
        cards2.add(new Card(5, '\u2660'));// ♠
        cards2.add(new Card(3, '\u2666'));// ♦
        cards2.add(new Card(5, '\u2665'));// ♥
        cards2.add(new Card(2, '\u2663'));// ♣
        cards2.add(new Card(3, '\u2660'));// ♠

        unstableSort(cards2);
        System.out.println("After unstable sort by number:");
        printList(cards2);
    }
}

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

shift elements greater than key to the right to keep stable order

cards.set(j + 1, key);

insert key at correct position preserving order

if(cards.get(j).number < cards.get(minIdx).number) {

using < picks leftmost min, keeps some order but is stable; original code used <= which caused instability

Output

Original list:

5♠ -> 3♦ -> 5♥ -> 2♣ -> 3♠ -> null

After stable sort by number:

2♣ -> 3♦ -> 3♠ -> 5♠ -> 5♥ -> null

After unstable sort by number:

2♣ -> 3♦ -> 3♠ -> 5♠ -> 5♥ -> null

Complexity Analysis

Time: O(n^2) for stable insertion sort because each element may shift past many others

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

vs Alternative: Stable insertion sort is slower but keeps order; unstable sorts like quicksort are faster but may reorder equal items

Edge Cases

Empty list

No sorting needed, list remains empty

DSA Java

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

All elements equal

Stable sort keeps original order unchanged

DSA Java

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

Single element list

No sorting needed, list remains same

DSA Java

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

When to Use This Pattern

When asked to sort data but keep the original order of equal items, use a stable sort like insertion sort or merge sort to preserve order.

Common Mistakes

Mistake: Using an unstable sort when stable order is required, causing equal items to reorder unexpectedly.
Fix: Choose a stable sorting algorithm or implement stability explicitly.

Mistake: Assuming all built-in sorts are stable; some are not depending on language and implementation.
Fix: Check documentation or use a known stable sort if order matters.

Summary

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

Use stable sorts when the order of equal items matters, like sorting by multiple keys.

The key insight is that stable sorts never swap equal elements out of their original sequence.

Practice

1. Which sorting algorithm is stable by default, meaning it keeps the original order of equal elements?

easy

A. Heap Sort

B. Merge Sort

C. Quick Sort

D. Selection Sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of equal elements unchanged after sorting.

2. Step 2: Identify stable sorting algorithms

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

3. Final Answer:

   Merge Sort -> Option B

4. Quick Check:

   Stable sort = Merge Sort [OK]

Hint: Stable sorts keep equal items in original order [OK]

Common Mistakes:

• Thinking Quick Sort is stable
• Confusing Heap Sort as stable
• Assuming Selection Sort preserves order

2. Which of the following is the correct Java syntax to call a stable sorting method on an array named arr?

easy

A. Collections.stableSort(arr);

B. Collections.sort(arr);

C. Arrays.stableSort(arr);

D. Arrays.sort(arr);

Solution

1. Step 1: Identify Java sorting methods

   Java's Arrays.sort() method sorts arrays and uses a stable sort for objects.

2. Step 2: Check method availability

   There is no stableSort method in Java's standard libraries. Collections.sort() works on lists, not arrays.

3. Final Answer:

   Arrays.sort(arr); -> Option D

4. Quick Check:

   Correct syntax for array sort = Arrays.sort(arr); [OK]

Hint: Use Arrays.sort for arrays, Collections.sort for lists [OK]

Common Mistakes:

• Using Collections.sort on arrays
• Assuming stableSort method exists
• Confusing array and list sorting methods

3. What is the output of the following Java code snippet?

class Item {
  int value;
  String name;
  Item(int v, String n) { value = v; name = n; }
  public String toString() { return name; }
}

Item[] arr = {
  new Item(2, "apple"),
  new Item(1, "banana"),
  new Item(2, "cherry"),
  new Item(1, "date")
};

Arrays.sort(arr, Comparator.comparingInt(i -> i.value));
for (Item i : arr) System.out.print(i + " ");

medium

A. banana date apple cherry

B. date banana cherry apple

C. apple cherry banana date

D. banana date cherry apple

Solution

1. Step 1: Understand sorting criteria and stability

   The array is sorted by value using Arrays.sort with a comparator. Java's TimSort is stable, so equal values keep original order.

2. Step 2: Trace sorting and output

   Items with value 1 are "banana" then "date" (original order). Items with value 2 are "apple" then "cherry". Sorted order: banana, date, apple, cherry.

3. Final Answer:

   banana date apple cherry -> Option A

4. Quick Check:

   Stable sort keeps equal values order: banana date apple cherry [OK]

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

Common Mistakes:

• Assuming unstable sort changes order of equal values
• Mixing up item names in output
• Ignoring stability of Java's Arrays.sort with comparator

4. The following code tries to sort an array of integers but does not preserve the order of equal elements. What is the main issue?

int[] arr = {4, 2, 4, 3};
Arrays.sort(arr);
// Expected stable sort but order of equal 4s changed

medium

A. Arrays.sort on primitives is not stable

B. Comparator is missing for stability

C. Array contains duplicates causing error

D. Arrays.sort cannot sort integers

Solution

1. Step 1: Check sorting method on primitive arrays

   Java's Arrays.sort on primitive types (like int[]) uses a dual-pivot quicksort which is not stable.

2. Step 2: Understand stability for primitives vs objects

   For objects, Java uses TimSort which is stable. For primitives, stability is not guaranteed, so equal elements may reorder.

3. Final Answer:

   Arrays.sort on primitives is not stable -> Option A

4. Quick Check:

   Primitive sort = unstable Arrays.sort [OK]

Hint: Primitive array sort in Java is unstable [OK]

Common Mistakes:

• Expecting stability on primitive arrays
• Thinking missing comparator causes instability
• Assuming duplicates cause errors

5. You have a list of employee records with fields id and salary. You want to sort by salary ascending but keep employees with the same salary in the order they were added. Which sorting approach is best?

hard

A. Use Heap Sort to guarantee order of equal salaries

B. Use Quick Sort for faster average performance ignoring stability

C. Use a stable sort like Merge Sort on the list by salary

D. Sort by id first, then by salary using unstable sort

Solution

1. Step 1: Understand requirement for stability

   We want to keep original order of employees with same salary, so stability is required.

2. Step 2: Choose sorting algorithm with stability

   Merge Sort is stable and sorts by salary while preserving order of equal salaries. Quick Sort and Heap Sort are not stable by default.

3. Final Answer:

   Use a stable sort like Merge Sort on the list by salary -> Option C

4. Quick Check:

   Stable sort needed for preserving order = Merge Sort [OK]

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

Common Mistakes:

• Choosing unstable sorts ignoring order preservation
• Sorting by id first without stable sort
• Assuming Heap Sort is stable