Stable Sort

A stable sorting algorithm maintains the relative order of elements with equal keys. For elements with the same key, their original order is preserved after sorting.

Some examples of stable sorting algorithms:

Insertion sort
Merge sort
Bubble sort
Counting sort

Whereas unstable algorithms like quicksort and heapsort do not guarantee maintaining original element order for equal keys.

Java - Stable merge sort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void mergeSort(int[] arr) {
  // Split into halves
  mergeSort(firstHalf); 
  mergeSort(secondHalf);
  
  // Merging logic preserves order of equal keys
}

void merge(int[] left, int[] right) {
  int indexL = 0, indexR = 0;

  while (indexL < left.length && indexR < right.length) {
    if (left[indexL] <= right[indexR]) {
      result.add(left[indexL++]);
    } else {
      result.add(right[indexR++]);
    }
  }  
}

C++ - Stable counting sort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
vector<int> countingSort(vector<int> arr) {
  
  vector<int> count(MAX_VAL);
  vector<int> result;

  // Count occurrences
  for(int i=0; i<arr.size(); i++) {
    count[arr[i]]++; 
  }

  // Build sorted result
  for(int i=0; i<MAX_VAL; i++) {
    while(count[i] > 0) {
      result.push_back(i);
      count[i]--;
    }
  }

  return result;
}

Python - Stable bubble sort:

1
2
3
4
5
6
7
8
9
def bubbleSort(arr):
  n = len(arr)

  for i in range(n-1):
    for j in range(n-i-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]

# Stable - equal keys not swapped

Stability is useful when order of equal keys matters, like sorting names by surname.

In sorting algorithms, “stable” refers to the preservation of the relative order of equal elements in the sorted output. In other words, if you have two equal elements A and B, and A appears before B in the input, A will still appear before B in the sorted output. Stability is important when you perform multiple rounds of sorting based on different keys. Stable sorting algorithms include Bubble Sort, Merge Sort, and Insertion Sort, among others.

In the context of stable sorting, it’s about preserving the relative order of elements that are considered equal according to the sorting criterion. This is particularly useful when you have multiple attributes and you sort by one attribute first and then by another.

Let’s consider a simple example where we want to sort an array of letters based on their uppercase versions. Our input array is: [a1, b1, A1, a2, A2, b2].

Before Sorting:

a1, b1, A1, a2, A2, b2

After Sorting (Unstable):

If we use an unstable sorting algorithm, we may get:

A1, A2, a1, a2, b1, b2

Notice that the relative orders of a1, a2 and b1, b2 are preserved, but A1, A2 have moved ahead of a1, a2.

After Sorting (Stable):

If we use a stable sorting algorithm, we get:

A1, a1, A2, a2, b1, b2

In this case, the relative orders of both lower and uppercase ‘A’ and ‘a’ are preserved.

The stable sort keeps the two ‘A’s and ‘a’s in the same relative positions (A1 before a1, A2 before a2), while also sorting the array.

This illustration shows how stability works in a sorting algorithm.

Let’s take Bubble Sort as an example of a stable sorting algorithm.

Java

Here is how you can implement Bubble Sort in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class StableBubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

C++

The C++ implementation is similar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Python

The Python code would look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [4, 2, 2, 8, 3, 3, 1]
bubble_sort(arr)
print(arr)

In all these implementations, the Bubble Sort algorithm preserves the relative order of equal elements, making it a stable sort. The if statement only triggers a swap if the condition is met, ensuring stability.