17. Stability and In Place Sorting Algorithms

These two concepts are essential for sorting algorithms since their method of sorting are all slightly different. This is good for understanding what the algorithm is actually doing to sort an array.

Stability

Sorting algorithm is stable if for all indexes $i$ and $j$ such that the $A[i] = A[j]$, if element $A[i]$ precedes element $A[j]$ in the original array, then element $A[i]$ also precedes element $A[j]$ in the sorted array.

In other words, sorting algorithms that maintain the relative order of elements with equal keys (equivalent elements retain their relative positions even after sorting) are called stable sorting algorithms. This is an important property: for example, we preserve the order of insertions (time stamp) even after sorting.

Which algorithms are stable?

$A$ is the array to be sorted
Let $R$ and $S$ be two elements of $A$ with the same key and $R$ appears earlier in the array than $S$:
- $R$ is at position $i$, and $S$ at position $j$, such that $i<j$
To show that algorithm is stable make sure that in the sorted output $R$ cannot appear after $S$
Satisfying these conditions will allow an algorithm to be stable.

Sorting algorithms:

Bubble sort is stable
Insertion sort is stable
Selection sort is not stable
Merge sort is stable
Quick sort is not stable

In Place vs Not In Place Sorting Algorithms

In Place Sort

If an algorithm needs $O(1)$ additional temporary memory. We rearrange elements inside the array itself.

Not In Place Sort

If an algorithm needs $\ge O(n)$ of additional memory. We move data between the orginial array and a temporary arrays.

In Place Can Get Weird

An algorithm like quick sort is technically in place, but it needs some space complexity for recursive calls.

In Place Sorting:

Bubble Sort
Insertion Sort
Quick Sort

Not In Place Sorting:

Merge Sort

Next Page →