The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
Show that any comparison based sorting algorithm can be made stable without increasing its complexity beyond a constant factor.
asked in Algorithms by Veteran (56.5k points) | 275 views
Don't swap when numbers are equal nt that the idea ?

2 Answers

+1 vote

Any given sorting algo which is not stable can be modified to be stable. There can be sorting algo specific ways to make it stable, but in general, any comparison based sorting algorithm which is not stable by nature can be modified to be stable by changing the key comparison operation so that the comparison of two keys considers position as a factor for objects with equal keys.

Key comparison operation is always satisfies transitivity property. So, complexity of stable sort shouldnot increase more than a constant factor.

answered by Veteran (112k points)
Plz correct me if wrong
–1 vote
answered by Active (2.5k points)
reshown by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,518 answers
75,287 users