Sorting Stability and When to Use Which Sort in DSA Javascript

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 placed in your hand.

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

'a' and 'b' show two different 5s to track order.

Dry Run Walkthrough

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

Goal: Sort the list so numbers are in order, but keep 5a before 5b and first 3 before second 3

Step 1: Compare 5a and 3, swap because 3 < 5a

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

Why: We want smaller numbers first, so 3 moves before 5a

Step 2: Compare 5a and 5b, no swap because equal and stable keeps order

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

Why: Stable sort keeps 5a before 5b since they are equal

Step 3: Compare 5b and 2, swap because 2 < 5b

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

Why: Smaller number 2 moves forward

Step 4: Compare 5b and 3, swap because 3 < 5b

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

Why: Smaller number 3 moves forward

Step 5: Compare 5a and 2, swap because 2 < 5a; then compare 5a and 3, no swap because 3 > 5a

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

Why: Smaller number 2 moves forward; 3 is not less than 5a so no swap

Step 6: Compare 3 and 2, swap because 2 < 3

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

Why: 2 moves to front as smallest

Result:

2 -> 3 -> 3 -> 5a -> 5b -> null
Order of equal numbers (3s and 5s) is kept the same as original

Annotated Code

DSA Javascript

class Node {
  constructor(value, label) {
    this.value = value;
    this.label = label; // to track original order
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(value, label) {
    const newNode = new Node(value, label);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
  }

  print() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + curr.label + ' -> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

function stableSortLinkedList(list) {
  if (!list.head || !list.head.next) return;

  let changed;
  do {
    changed = false;
    let curr = list.head;
    while (curr.next) {
      // Compare values
      if (curr.value > curr.next.value) {
        // Swap values and labels to keep nodes stable
        [curr.value, curr.next.value] = [curr.next.value, curr.value];
        [curr.label, curr.next.label] = [curr.next.label, curr.label];
        changed = true;
      }
      curr = curr.next;
    }
  } while (changed);
}

// Driver code
const list = new LinkedList();
list.append(5, 'a');
list.append(3, '');
list.append(5, 'b');
list.append(2, '');
list.append(3, '');

console.log('Before sorting:');
list.print();
stableSortLinkedList(list);
console.log('After stable sorting:');
list.print();

if (!list.head || !list.head.next) return;

handle empty or single node list - no sorting needed

do { changed = false; let curr = list.head; while (curr.next) { ... } } while (changed);

repeat passes until no swaps - bubble sort approach

if (curr.value > curr.next.value) { swap values and labels; changed = true; }

swap only if current value is greater to keep ascending order and maintain stability by swapping labels with values

curr = curr.next;

advance to next node to compare pairs

Output

Before sorting:

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

After stable sorting:

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

Complexity Analysis

Time: O(n²) because bubble sort compares pairs repeatedly until sorted

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

vs Alternative: More efficient sorts like merge sort are O(n log n) and stable, better for large data; bubble sort is simple but slow

Edge Cases

empty list

function returns immediately, no error

DSA Javascript

if (!list.head || !list.head.next) return;

single element list

function returns immediately, no sorting needed

DSA Javascript

if (!list.head || !list.head.next) return;

all elements equal

no swaps happen, original order preserved

DSA Javascript

if (curr.value > curr.next.value) { ... }

When to Use This Pattern

When you need to keep the original order of equal items after sorting, look for a stable sort pattern because it preserves order while sorting.

Common Mistakes

Mistake: Swapping nodes instead of just values can break stability or complicate code.
Fix: Swap only the values and labels inside nodes to keep the node order stable.

Mistake: Using unstable sorts when order of equal elements matters.
Fix: Choose stable sorting algorithms like merge sort or bubble sort for stable results.

Summary

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

Use stable sorts when the order of equal elements matters, like sorting cards or records with ties.

The key is to swap values carefully without changing the relative order of equal elements.

Practice

1. What does it mean when a sorting algorithm is stable?

easy

A. It keeps the original order of equal elements after sorting

B. It sorts elements faster than unstable algorithms

C. It uses less memory than unstable algorithms

D. It always sorts in ascending order

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of items with equal keys unchanged.

2. Step 2: Compare with other options

   Speed, memory use, or sorting order do not define stability.

3. Final Answer:

   It keeps the original order of equal elements after sorting -> Option A

4. Quick Check:

   Stable sort = keeps equal elements order [OK]

Hint: Stable means equal items keep their original order [OK]

Common Mistakes:

• Confusing stability with speed
• Thinking stability means sorting ascending only
• Assuming stable sorts use less memory

2. Which of the following is the correct way to call JavaScript's built-in sort method to sort numbers in ascending order?

easy

A. arr.sort()

B. arr.sort((a, b) => a + b)

C. arr.sort((a, b) => b - a)

D. arr.sort((a, b) => a - b)

Solution

1. Step 1: Understand JavaScript's default sort

   By default, arr.sort() sorts elements as strings, not numbers.

2. Step 2: Use compare function for numeric ascending

   The compare function (a, b) => a - b sorts numbers ascending correctly.

3. Final Answer:

   arr.sort((a, b) => a - b) -> Option D

4. Quick Check:

   Numeric ascending sort uses (a, b) => a - b [OK]

Hint: Use (a, b) => a - b for ascending numeric sort [OK]

Common Mistakes:

• Using arr.sort() alone for numbers
• Using (a, b) => b - a for ascending order
• Using (a, b) => a + b which is invalid

3. Consider the array of objects:

const items = [
  {name: 'apple', price: 50},
  {name: 'banana', price: 20},
  {name: 'cherry', price: 50},
  {name: 'date', price: 20}
];
items.sort((a, b) => a.price - b.price);

What will be the order of items after sorting?

medium

A. [{banana,20}, {date,20}, {cherry,50}, {apple,50}]

B. [{date,20}, {banana,20}, {cherry,50}, {apple,50}]

C. [{banana,20}, {date,20}, {apple,50}, {cherry,50}]

D. [{date,20}, {banana,20}, {apple,50}, {cherry,50}]

Solution

1. Step 1: Understand the sort comparator

   The comparator sorts by price ascending: 20 then 50.

2. Step 2: Check stability of JavaScript sort

   JavaScript's sort is stable in modern engines, so equal price items keep original order.

3. Step 3: Apply stability to equal price items

   For price 20, original order is banana then date; for 50, apple then cherry.

4. Final Answer:

   [{banana,20}, {date,20}, {apple,50}, {cherry,50}] -> Option C

5. Quick Check:

   Stable sort keeps equal price order [OK]

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

Common Mistakes:

• Assuming unstable sort changes order of equal items
• Mixing up banana and date order
• Ignoring stability of JavaScript sort

4. The following code tries to sort an array of strings by length, which may not keep the original order of equal length strings:

const arr = ['bat', 'cat', 'apple', 'dog'];
arr.sort((a, b) => a.length - b.length);

What is the main reason the original order of equal length strings might not be preserved?

medium

A. Strings cannot be sorted by length

B. JavaScript's sort is unstable in some engines

C. The comparator function is incorrect

D. The array contains duplicates

Solution

1. Step 1: Check comparator correctness

   The comparator (a, b) => a.length - b.length correctly compares string lengths.

2. Step 2: Understand JavaScript sort stability

   JavaScript's sort is stable in modern engines but may be unstable in older engines, causing order change.

3. Final Answer:

   JavaScript's sort is unstable in some engines -> Option B

4. Quick Check:

   Unstable sort breaks equal element order [OK]

Hint: Old JS engines have unstable sort, losing order [OK]

Common Mistakes:

• Blaming comparator function
• Thinking strings can't be sorted by length
• Assuming duplicates cause instability

5. You have a list of student records with name and score. You want to sort by score ascending but keep the original order for students with the same score. Which sorting algorithm should you choose and why?

hard

A. MergeSort, because it is stable and sorts efficiently

B. QuickSort, because it is fast but unstable

C. HeapSort, because it uses less memory

D. BubbleSort, because it is simple and stable

Solution

1. Step 1: Identify need for stability

   We want to keep original order for equal scores, so stability is required.

2. Step 2: Choose algorithm with stability and efficiency

   MergeSort is stable and efficient (O(n log n)), suitable for this task.

3. Step 3: Compare other options

   QuickSort is fast but unstable; HeapSort is unstable; BubbleSort is stable but inefficient.

4. Final Answer:

   MergeSort, because it is stable and sorts efficiently -> Option A

5. Quick Check:

   Stable + efficient = MergeSort [OK]

Hint: Stable and efficient sort for equal keys: MergeSort [OK]

Common Mistakes:

• Choosing QuickSort ignoring instability
• Picking BubbleSort despite inefficiency
• Confusing HeapSort as stable