The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

Show that any comparison based sorting algorithm can be made stable without increasing its complexity beyond a constant factor.

+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.

http://www.geeksforgeeks.org/stability-in-sorting-algorithms/

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,856 questions

47,522 answers

145,900 comments

62,280 users