why stability is important in sorting algorithms?

Ans1: For parallelization purposes? eg: merge sort is stable and can be parallelized well and so is quicksort.


Ans2:

Background: a "stable" sorting algorithm keeps the items with the same sorting key in order. Suppose we have a list of 5-letter words:

peach straw apple spork

Stable-sorting by the first letter gives us:

apple peach straw spork

In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since 'straw' appears

before 'spork' in the input, it also appears before 'spork' in the output).

Ans 3:
There's a few reasons why stability can be important. One is that, if two records don't need to be swapped by swapping them you can cause a memory update, a

page is marked dirty, and needs to be re-written to disk (or another slow medium).

Ans 4:
  Stable sort will allways return same solution (permutation)

Ans 5:

Sorting stability means that records with the same key retain their relative order before and after the sort.

So stability matters if, and only if, the problem you're solving requires retention of that relative order.

If you don't need stability, you can use a fast, memory-sipping algorithm from a library, like heapsort or quicksort, and forget about it.

If you need stability, it's more complicated. Stable algorithms have higher big-O CPU and/or memory usage than unstable algorithms. So when you have a large

data set, you have to pick between beating up the CPU or the memory. If you're constrained on both CPU and memory, you have a problem. A good compromise

stable algorithm is a binary tree sort;


memory usage on Merge Sort is O(N), while on Quicksort it's O(log N).