Question

C++

What does it mean for a sorting algorithm to be "stable"?

Wikipedia has a list of all known sorting algorithms. Which one's average is the worst and what is its Big O? (I just wanted to make you see that list.)

Answer 1

A sorting algorithm is said to be stable if the output of the algorithm is same as the array would have been sorted in ascending or descending order. It preserves the order of record which have the equal keys. A stable algorithm is used to solve any small errors.

The sorting algorithm which has the worst average case complexity are:

1) Insertion Sort O(n^{​​​​​​2}​​​​​)

2) Selection Sort O(n^{​​​​​​2})

3) Cycle Sort O(n^{​​​​​​2}​​​​​)

4) Strand Sort O(n^{​​​​​​2})

5) Cocktail Shaker Sort O(n^{​​​​​2}​​​​​)

^​​6) Comb Sort O(n^{​​​​​​2})

7) Gnome Sort O(n^{​​​​​​2}​​​​​)

8) Odd even sort O(n^{​​​​​​2})

All these sorting algorithms have the worst average case complexity with Big O as O(n^{​​​​​​2}​​​​​)

If you liked the solution then give a thumbs up ? it will be really appreciated ?