1

I understand the significance of the in place property of a sorting algorithm.

I know that stability helps in maintaining the relative order, but does the algorithm's stability property affect its performance?

Cœur
  • 37,241
  • 25
  • 195
  • 267
Abhinandan Satpute
  • 2,558
  • 6
  • 25
  • 43
  • 2
    Does this question : http://programmers.stackexchange.com/questions/247440/what-does-it-mean-for-a-sorting-algorithm-to-be-stable help you ? I don't quite get what you are asking here : are you simply looking for a definition of 'stable' ? – Alexandre C. Apr 19 '16 at 17:50
  • It is necessary when the calling code wants it. I.e. it a matter of specific application. In other words it is up to you: when you need stable sort for your purposes, you use stable sort. – AnT stands with Russia Apr 19 '16 at 17:50
  • Sorting algorithms don't _have to_ be stable. But you, as a user, want to know if it's stable or not (if you rely on this property). – Sergio Tulentsev Apr 19 '16 at 17:50
  • @AlexandreC. Yeah.It did help but I would like to know more about it's effect on performance if it has any. – Abhinandan Satpute Apr 19 '16 at 17:57
  • 2
    If you have a performance question then answer it with science. Implement a stable sort and an unstable sort, run them both, and soon you will know which one is faster. – Eric Lippert Apr 19 '16 at 17:57
  • This will help you : https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms – Alexandre C. Apr 19 '16 at 17:58
  • *[Stability:](https://en.wikipedia.org/wiki/Sorting_algorithm) stable sorting algorithms maintain the relative order of records with equal keys (i.e., values).* If there is undefined behavior when 2 values are the same, then this is usually considered unstable. – But I'm Not A Wrapper Class Apr 19 '16 at 17:59
  • 1
    Related: http://stackoverflow.com/a/8312128/56778 – Jim Mischel Apr 19 '16 at 19:23

1 Answers1

1

From Wikipedia:

A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

About your questions:

Does the algorithm's stability property affect it's performance?

I think the stability of an algorithm is not related to their efficiency, are two separate concepts.

Stability is a property that a sorting algorithm can have or not depending to it nature, but is like a 'side effect', doesn't impact directly in its performance.

An unstable algorithm can easily be converted to stable by adding an extra index key to compare if the primary keys match.

If your question is like How implement a stable sorting algorithm, then stability probably will impact since it is an extra requirement to comply.

Why is it necessary?

You can read about the benefits of stable algorithm in this question.

Community
  • 1
  • 1
Arturo Menchaca
  • 15,783
  • 1
  • 29
  • 53