Sorting

Stable vs Unstable

Sorting algorithm could be either stable or unstable depending on their ways of managing redundant element. For instance lets say we have array [1, 5, 3, 4, 3, 2], and for repetitive element we put tag to make them distinguishable [1, 5, 3(1), 4, 3(2), 2]. Now for stable sorting algorithm the order of these repetitive elements are preserve after sorting is completed, while unstable sorting is not.

So for our example, after stable sort -> [1, 2, 3(1), 3(2), 4, 5] after unstable sort -> [1, 2, 3(2), 3(1), 4, 5]

stable sorting algorithms

• Insertion Sort
• Merge sort
• Bubble sort
• Counting sort

unstable sorting algorithms

• Selection sort
• Heap sort
• Shell sort
• Quick sort

in-place sorting algorithm

The sorting algorithm that uses negligible amount of additional memory is an inplace algorithm.

In-place sorting algorihtms

- Insertion sort
- Selection sort
- Bubble sort
- Shell sort
- Heap sort
- Quick sort (depends on the definition) ## Not In-place sorting algorithms
- Merge sort
- Counting sort
- Radix sort
- Bucket Sort