1 votes 1 votes Show that any comparison based sorting algorithm can be made stable without increasing its complexity beyond a constant factor. Algorithms algorithms descriptive time-complexity non-gate + – dd asked Feb 21, 2017 dd 2.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply Anand Vijayan commented Feb 23, 2017 reply Follow Share Don't swap when numbers are equal ...is nt that the idea ? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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/ https://en.wikipedia.org/wiki/Sorting_algorithm#Stability https://en.wikipedia.org/wiki/Comparison_sort srestha answered Feb 22, 2017 srestha comment Share Follow See 1 comment See all 1 1 comment reply srestha commented Feb 22, 2017 reply Follow Share Plz correct me if wrong 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/exams/prac_quiz1sol.pdf Problem 3 Kai answered Feb 21, 2017 reshown Feb 23, 2017 by Kai Kai comment Share Follow See all 0 reply Please log in or register to add a comment.