Stability in Sorting Algorithms

Introduction

Stability is an important criterion for analyzing sorting algorithms. Understanding whether an algorithm is stable or unstable helps determine its suitability for different applications, especially when dealing with complex data structures with multiple fields.

What is Stability?

A sorting algorithm is considered stable if it maintains the relative order of equal elements as they appeared in the original array.

Formal Definition

If two items have the same value for the sorting key, they should appear in the same relative order in the sorted output as they appeared in the original input.

Key Points

Stability only matters when sorting objects with multiple fields
It's not relevant for simple data types like integers (unless they have associated metadata)
Stable algorithms preserve secondary sorting criteria

Example: Student Records

Let's consider an array of students that is already sorted alphabetically by name:

Original Array (Sorted by Name)

const students = [
  { name: 'Anil', marks: 50 },
  { name: 'Ayan', marks: 80 }, 
  { name: 'Piyush', marks: 50 },
  { name: 'Ramesh', marks: 80 }
];

Task: Sort this array by marks in ascending order while maintaining alphabetical order for students with the same marks.

Stable vs Unstable Output

Stable Algorithm Output

When using a stable sorting algorithm:

// Stable output - maintains original relative order for equal marks
const stableOutput = [
  { name: 'Anil', marks: 50 },     // Anil appears before Piyush (both have 50 marks)
  { name: 'Piyush', marks: 50 },   // Original relative order maintained
  { name: 'Ayan', marks: 80 },     // Ayan appears before Ramesh (both have 80 marks)  
  { name: 'Ramesh', marks: 80 }    // Original relative order maintained
];

Why it's stable: Students with the same marks maintain their original alphabetical order.

Unstable Algorithm Output

An unstable sorting algorithm might produce:

// Unstable output - original relative order may be changed
const unstableOutput = [
  { name: 'Piyush', marks: 50 },   // Piyush now appears before Anil
  { name: 'Anil', marks: 50 },     // Original order disturbed
  { name: 'Ramesh', marks: 80 },   // Ramesh now appears before Ayan
  { name: 'Ayan', marks: 80 }      // Original order disturbed
];

Why it's unstable: The relative order of equal elements has been changed compared to the original array.

Common Stable and Unstable Algorithms

Stable Algorithms ✅

Bubble Sort
Insertion Sort
Merge Sort

Unstable Algorithms ❌

Selection Sort
Quick Sort
Heap Sort

Detailed Analysis

Why Bubble Sort is Stable

Bubble Sort Mechanism:

Always compares adjacent elements: arr[i] with arr[i+1]
Only swaps if arr[i] > arr[i+1]
If arr[i] == arr[i+1], no swap occurs

Stability Explanation: Since equal elements are never swapped during adjacent comparisons, their relative order is preserved throughout the entire sorting process.

// Bubble Sort Implementation - Stable
function bubbleSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      // Only swap if strictly greater (maintains stability)
      if (arr[j].marks > arr[j + 1].marks) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  
  return arr;
}
 
// Example usage
const students = [
  { name: 'Anil', marks: 50 },
  { name: 'Ayan', marks: 80 },
  { name: 'Piyush', marks: 50 },
  { name: 'Ramesh', marks: 80 }
];
 
console.log(bubbleSort([...students]));
// Output maintains relative order for equal marks

Why Selection Sort is Unstable

Selection Sort Mechanism:

Find the maximum element in the array
Swap it with the last element
Repeat for the remaining array (excluding the last sorted element)

Instability Explanation: Selection sort performs long-distance swaps. When it swaps the maximum element with the last element, it can move an element past other equal elements, disrupting their original relative order.

// Selection Sort Implementation - Unstable
function selectionSort(arr) {
  const n = arr.length;
  
  for (let i = n - 1; i > 0; i--) {
    // Find the maximum element in the unsorted portion
    let maxIndex = 0;
    for (let j = 1; j <= i; j++) {
      if (arr[j].marks > arr[maxIndex].marks) {
        maxIndex = j;
      }
    }
    
    // Swap maximum element with last element of unsorted portion
    // This long-distance swap can disrupt relative order
    [arr[maxIndex], arr[i]] = [arr[i], arr[maxIndex]];
  }
  
  return arr;
}

Example of Instability:

// Original array with objects having same values
const example = [
  { id: 'A', value: 3 },
  { id: 'B', value: 3 },
  { id: 'C', value: 3 },
  { id: 'D', value: 1 }
];
 
// After selection sort, the relative order of equal elements may change
// Original order: A, B, C (all with value 3)
// After sorting: C, B, A (order disturbed due to long-distance swaps)

When Does Stability Matter?

Stability is Important When:

✅ Sorting objects with multiple fields
✅ You want to maintain secondary sorting criteria
✅ Working with databases or structured data
✅ User interface elements need consistent ordering
✅ Implementing multi-level sorting

Stability is Not Important When:

❌ Sorting simple data types (integers, strings) without associated objects
❌ All elements in the array are unique
❌ Only performance matters, not order preservation
❌ One-time sorting with no secondary criteria

Real-World Example

Imagine an e-commerce website displaying products:

// Products already sorted by category
const products = [
  { name: 'Laptop', category: 'Electronics', price: 1000 },
  { name: 'Phone', category: 'Electronics', price: 800 },
  { name: 'Shirt', category: 'Clothing', price: 50 },
  { name: 'Jeans', category: 'Clothing', price: 80 },
  { name: 'Novel', category: 'Books', price: 15 },
  { name: 'Textbook', category: 'Books', price: 100 }
];
 
// Sort by price using a stable algorithm
// Products with same price maintain their category-based ordering
function stableSortByPrice(products) {
  // Using JavaScript's built-in sort (which is stable in modern browsers)
  return products.sort((a, b) => a.price - b.price);
}

Practical Implications

JavaScript's Built-in Sort

// JavaScript's Array.sort() is stable (as of ES2019)
const students = [
  { name: 'Alice', grade: 85 },
  { name: 'Bob', grade: 90 },
  { name: 'Charlie', grade: 85 }
];
 
// Sort by grade - maintains original order for equal grades
const sortedStudents = students.sort((a, b) => a.grade - b.grade);
console.log(sortedStudents);
// Result: Alice appears before Charlie (both have 85) maintaining original order

Multi-level Sorting Example

// First sort by department, then by salary
const employees = [
  { name: 'John', department: 'Engineering', salary: 80000 },
  { name: 'Jane', department: 'Marketing', salary: 75000 },
  { name: 'Bob', department: 'Engineering', salary: 80000 },
  { name: 'Alice', department: 'Marketing', salary: 75000 }
];
 
// Sort by department first
employees.sort((a, b) => a.department.localeCompare(b.department));
 
// Then sort by salary (stable sort maintains department grouping)
employees.sort((a, b) => a.salary - b.salary);
 
console.log(employees);
// Employees with same salary maintain their departmental grouping

Custom Stable Sort Implementation

// Merge Sort - Always Stable
function mergeSort(arr, compareFunction) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid), compareFunction);
  const right = mergeSort(arr.slice(mid), compareFunction);
  
  return merge(left, right, compareFunction);
}
 
function merge(left, right, compareFunction) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while (leftIndex < left.length && rightIndex < right.length) {
    // Use <= to maintain stability (prefer left element when equal)
    if (compareFunction(left[leftIndex], right[rightIndex]) <= 0) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
 
// Usage
const data = [
  { name: 'Anil', marks: 50 },
  { name: 'Ayan', marks: 80 },
  { name: 'Piyush', marks: 50 },
  { name: 'Ramesh', marks: 80 }
];
 
const sorted = mergeSort(data, (a, b) => a.marks - b.marks);
console.log(sorted);
// Maintains relative order for equal marks

Summary

Algorithm	Stability	Reason
Bubble Sort	Stable	Only swaps adjacent elements if strictly greater
Insertion Sort	Stable	Inserts elements without disturbing equal elements
Merge Sort	Stable	Merge operation preserves order of equal elements
Selection Sort	Unstable	Long-distance swaps can disrupt relative order
Quick Sort	Unstable	Partitioning can move equal elements arbitrarily
Heap Sort	Unstable	Heap operations don't preserve relative order

Testing Stability

// Function to test if a sorting algorithm is stable
function testStability(sortFunction) {
  // Create test data with objects having same values but different identifiers
  const testData = [
    { id: 'A', value: 5 },
    { id: 'B', value: 3 },
    { id: 'C', value: 5 },
    { id: 'D', value: 3 },
    { id: 'E', value: 5 }
  ];
  
  console.log('Original order:', testData.map(item => item.id).join(', '));
  
  const sorted = sortFunction([...testData]);
  console.log('After sorting:', sorted.map(item => item.id).join(', '));
  
  // Check if relative order is maintained for equal values
  const value3Items = sorted.filter(item => item.value === 3);
  const value5Items = sorted.filter(item => item.value === 5);
  
  console.log('Items with value 3:', value3Items.map(item => item.id).join(', '));
  console.log('Items with value 5:', value5Items.map(item => item.id).join(', '));
  
  // For stable sort: B should come before D, A should come before C and E
  const isStable = value3Items[0].id === 'B' && 
                   value3Items[1].id === 'D' &&
                   value5Items[0].id === 'A' &&
                   value5Items[1].id === 'C' &&
                   value5Items[2].id === 'E';
  
  console.log('Is stable:', isStable);
  return isStable;
}
 
// Test with JavaScript's built-in sort (stable)
testStability(arr => arr.sort((a, b) => a.value - b.value));

Conclusion

Stability in sorting algorithms is a crucial property when working with complex data structures. While it doesn't affect the correctness of sorting simple data types, it becomes essential when maintaining relationships between multiple fields or when implementing multi-level sorting criteria.

Understanding stability helps in choosing the right algorithm for specific use cases:

Use stable algorithms when order preservation matters
Use unstable algorithms when performance is the primary concern and stability is not required

Remember: A stable algorithm maintains the relative order of equal elements, while an unstable algorithm may change this order during the sorting process.

Key Takeaways

Stability matters only when sorting objects with multiple fields
JavaScript's Array.sort() is stable (ES2019+)
Stable algorithms preserve secondary sorting criteria
Choose wisely based on your specific requirements
Test your assumptions when stability is critical for your application

Sorting in JavaScript Bubble Sort