87

Stable Sorting

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.

Some Sorting Algorithm is stable by nature like Insertion Sort, Merge Sort and Bubble Sort etc.

Sorting Algorithm is not stable like Quick Sort, Heap Sort etc.

Another Definition of Stable Sorting:

A Stable Sort is one which preserves the original order of input set, where the comparison algorithm does not distinguish between two or more items. A Stable Sort will guarantee that the original order of data having the same rank is preserved in the output.

---

In Place Sorting Algorithm:

1. An In-Place Sorting Algorithm directly modifies the list that is received as input instead of creating a new list that is then modified.
2. In this Sorting, a small amount of extra space it uses to manipulate the input set. In other Words, the output is placed in the correct position while the algorithm is still executing, which means that the input will be overwritten by the desired output on run-time.
3. In-Place, Sorting Algorithm updates input only through replacement or swapping of elements.
4. An algorithm which is not in-place is sometimes called not-in-Place or out of Place.
5. An Algorithm can only have a constant amount of extra space, counting everything including function call and Pointers, Usually; this space is O (log n).

Note:

1. Bubble sort, insertion sort, and selection sort are in-place sorting algorithms. Because only swapping of the element in the input array is required.
2. Bubble sort and insertion sort can be applying as stable algorithms but selection sort cannot (without significant modifications).
3. Merge sort is a stable algorithm but not an in-place algorithm. It requires extra array storage.
4. Quicksort is not stable but is an in-place algorithm.
5. Heap sort is an in-place algorithm but is not stable.

---