Sorting Stability and When to Use Which Sort in DSA C

Mental Model

Stable sorting keeps equal items in the same order as before. 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 laid out on the table.

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

'a' and 'b' show two different items with the same value 5.
Stable sort keeps 5a before 5b after sorting.

Dry Run Walkthrough

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

Goal: Sort the list so values are in ascending order, keeping 5a before 5b because they have the same value

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

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

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

Step 2: compare 5a and 5b, no swap because values equal and stable sort keeps order

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

Why: Stable sort keeps original order of equal values

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

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

Why: Smaller value 2 moves before 5b

Step 4: compare 5a and 2, swap because 2 < 5a

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

Why: 2 moves before 5a to keep ascending order

Step 5: compare 3 and 2, swap because 2 < 3

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

Why: 2 moves to front as smallest value

Result:

2 -> 3 -> 5a -> 5b -> null (stable order kept for equal 5s)

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Node structure for linked list with value and label
typedef struct Node {
    int value;
    char label;
    struct Node* next;
} Node;

// Create new node
Node* newNode(int value, char label) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value;
    node->label = label;
    node->next = NULL;
    return node;
}

// Print list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d%c -> ", curr->value, curr->label);
        curr = curr->next;
    }
    printf("null\n");
}

// Stable insertion sort on linked list
Node* insertionSort(Node* head) {
    if (head == NULL) return NULL;
    Node* sorted = NULL;
    Node* curr = head;
    while (curr != NULL) {
        Node* next = curr->next;
        // Insert curr into sorted list
        if (sorted == NULL || curr->value < sorted->value) {
            curr->next = sorted;
            sorted = curr;
        } else {
            Node* s = sorted;
            // Find position to insert curr
            while (s->next != NULL && s->next->value <= curr->value) {
                s = s->next;
            }
            curr->next = s->next;
            s->next = curr;
        }
        curr = next;
    }
    return sorted;
}

int main() {
    // Create list: 5a -> 3 -> 5b -> 2
    Node* head = newNode(5, 'a');
    head->next = newNode(3, ' ');
    head->next->next = newNode(5, 'b');
    head->next->next->next = newNode(2, ' ');

    printf("Original list:\n");
    printList(head);

    head = insertionSort(head);

    printf("Sorted list (stable):\n");
    printList(head);

    return 0;
}

while (curr != NULL) {

iterate over each node to insert into sorted list

if (sorted == NULL || curr->value < sorted->value) {

insert at head if sorted list empty or curr smaller than head

while (s->next != NULL && s->next->value <= curr->value) {

find position to insert curr keeping stable order for equal values

curr->next = s->next; s->next = curr;

insert curr node after s to maintain sorted order

curr = next;

advance to next node in original list

Output

Original list:

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

Sorted list (stable):

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

Complexity Analysis

Time: O(n^2) because insertion sort compares and inserts each node in sorted list

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

vs Alternative: Stable sorts like insertion sort keep order of equal items but can be slower; unstable sorts like quicksort are faster but may reorder equal items

Edge Cases

empty list

returns NULL without error

DSA C

if (head == NULL) return NULL;

single element list

returns the same single node as sorted

DSA C

if (head == NULL) return NULL;

all elements equal

keeps original order because insertion uses <= in comparison

DSA C

while (s->next != NULL && s->next->value <= curr->value) {

When to Use This Pattern

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

Common Mistakes

Mistake: Using < instead of <= in insertion position check, breaking stability
Fix: Use <= in while condition to keep equal items in original order

Summary

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

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

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

Practice

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

easy

A. It sorts elements in descending order

B. It uses less memory than unstable sorts

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

D. It always sorts in linear time

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of elements that compare equal unchanged.

2. Step 2: Compare options with definition

   Only It keeps the original order of equal elements after sorting matches this definition exactly.

3. Final Answer:

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

4. Quick Check:

   Stable sort = keeps order of equal elements [OK]

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

Common Mistakes:

• Confusing stability with sorting order
• Thinking stability means faster sorting
• Assuming stability relates to memory use

2. Which of the following is the correct syntax to call the qsort function in C for sorting an array arr of integers with n elements?

easy

A. qsort(arr, n, compare, sizeof(int));

B. qsort(arr, n, sizeof(int), compare);

C. qsort(arr, sizeof(int), n, compare);

D. qsort(arr, compare, n, sizeof(int));

Solution

1. Step 1: Recall qsort parameter order

   The qsort function parameters are: pointer to array, number of elements, size of each element, and comparison function pointer.

2. Step 2: Match parameters with options

   qsort(arr, n, sizeof(int), compare); matches this order exactly: arr, n, sizeof(int), compare.

3. Final Answer:

   qsort(arr, n, sizeof(int), compare); -> Option B

4. Quick Check:

   qsort syntax = arr, n, size, compare [OK]

Hint: Remember qsort: array, count, size, compare function [OK]

Common Mistakes:

• Mixing up size and count parameters
• Placing compare function in wrong position
• Using wrong order of arguments

3. Consider the following C code snippet using bubble sort on an array of structs with an integer key and a character value. Which output shows the array after sorting by key, preserving stability?

typedef struct {
  int key;
  char value;
} Item;

void bubbleSort(Item arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-i-1; j++) {
      if (arr[j].key > arr[j+1].key) {
        Item temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

int main() {
  Item arr[5] = {{2, 'a'}, {3, 'b'}, {2, 'c'}, {1, 'd'}, {3, 'e'}};
  bubbleSort(arr, 5);
  for (int i = 0; i < 5; i++) {
    printf("%d%c ", arr[i].key, arr[i].value);
  }
  return 0;
}

medium

A. 1d 2a 2c 3b 3e

B. 1d 2c 2a 3e 3b

C. 1d 2c 2a 3b 3e

D. 1d 2a 2c 3e 3b

Solution

1. Step 1: Understand bubble sort stability

   Bubble sort is stable, so equal keys keep their original order.

2. Step 2: Trace sorting of array

   Original order for key=2 is 'a' then 'c', for key=3 is 'b' then 'e'. After sorting by key, order is 1d, 2a, 2c, 3b, 3e.

3. Final Answer:

   1d 2a 2c 3b 3e -> Option A

4. Quick Check:

   Bubble sort stable = keeps order of equal keys [OK]

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

Common Mistakes:

• Assuming bubble sort is unstable
• Swapping equal keys and changing order
• Mixing up output order of equal keys

4. The following code attempts to sort an array using selection sort but does not preserve stability. What change fixes this to make it stable?

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    int min_idx = i;
    for (int j = i+1; j < n; j++) {
      if (arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }
    int temp = arr[min_idx];
    arr[min_idx] = arr[i];
    arr[i] = temp;
  }
}

medium

A. Sort array in descending order

B. Use bubble sort instead of selection sort

C. Change comparison to <= instead of <

D. Replace swap with shifting elements to insert min element

Solution

1. Step 1: Identify why selection sort is unstable

   Selection sort swaps min element directly, which can reorder equal elements and break stability.

2. Step 2: Fix by shifting elements

   Instead of swapping, shift elements right and insert min element at correct position to keep order.

3. Final Answer:

   Replace swap with shifting elements to insert min element -> Option D

4. Quick Check:

   Stable selection sort = shift, not swap [OK]

Hint: Shift elements instead of swap for stable selection sort [OK]

Common Mistakes:

• Just changing comparison operator
• Switching to bubble sort without reason
• Sorting in wrong order

5. You have a large dataset with many duplicate keys and need to sort it by key while preserving the order of duplicates. The dataset is too large to fit in memory, so you must use external sorting. Which sorting algorithm is best suited for this task?

hard

A. External merge sort because it is stable and handles large data

B. Quick sort because it is fastest in average case

C. Heap sort because it uses constant memory

D. Selection sort because it is simple to implement

Solution

1. Step 1: Understand requirements for large data and stability

   Large data needs external sorting; stability is required to keep duplicate order.

2. Step 2: Match algorithm features

   External merge sort is stable and designed for large data using disk; quicksort and heapsort are unstable and in-memory; selection sort is inefficient.

3. Final Answer:

   External merge sort because it is stable and handles large data -> Option A

4. Quick Check:

   Large stable sort = external merge sort [OK]

Hint: Use external merge sort for large stable sorting [OK]

Common Mistakes:

• Choosing quicksort ignoring stability
• Picking heapsort without external support
• Using simple sorts for large data