Sorting - which will perform Better

Question

If input is sorted in reverse order , then which sorting algorithm will perform best -

A) Insertion Sort

B) Merge Sort

C) Heap Sort

D) Quick Sort

Comments

merge sort ????

---

reason ?

Answer 1

C) HeapSort

Reference:http://www.sorting-algorithms.com/reversed-initial-order

Comments

can u explain the behaviour ?

---

HERE THE ANALYSIS-ALL ARE COMPARISON BASED SORTING ....BEST CASE is n*logn...

here its strict reverse order.

1.INSERTION SORT- would take O(n^2)...swapping the element take n^2 times .

2.QUICK sort - take here O(n^2)...due to unbalanced tree form at each step.tree would have height n with n(n-1)/2 comparisons in total

3 .HEAP sort - take always O(n*logn){balancing tree take logn and it happens for n elements}

4.MERGE sort - take here O(n/2*logn) at each level n/2 comparisons ...and its done for logn height of tree....

SO BEST HERE IS MERGE SORT

---

A​nswer is Heap Sort..

And how r u taking  n/2 comparisons at each level in merge sort ?

---

https://www.youtube.com/watch?v=ZZuD6iUe3Pc ...WATCH IT and pause at 2:18 ...and see which is better in reversed order ....MERGE OR HEAP ....try ur brain ...man!!