0

All of these sorting algorithms have an average case of O(n log n), so I would just like to know how I would be able to differentiate between these three sorting algorithms if I could run tests but not know which sorting algorithm was being run.

unkulunkulu
  • 11,576
  • 2
  • 31
  • 49
clay
  • 65
  • 2
  • 6

2 Answers2

1

another difference between Heap and Merge sort you may want to concern is, Heap is not stable sort, but Mergesort is.

here is a table(link below), you could find (almost) any information about comparison sort algorithms you want.

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Kent
  • 189,393
  • 32
  • 233
  • 301
-2

heapsort is a inplace sorting algorithm , we don't need extra storage to sort the elements but mergesort is not inplace sorting algorithm , we required extra storage , in merge procedure , to sort the elements.The worst case running time of quicksort is O(n^2) that differentiate it form heapsort and mergesort

There are many cases in which performance of these algorithms are different. 

    For example.
        if all input element are same. 
   then, heapsort will run in O(n) time
         quicksort will run in O(n^2) time. (if last element is a pivote element)
   and,
         mergesort is going to take O(logn) time.
siddstuff
  • 1,215
  • 4
  • 16
  • 37
  • correct quicksort will not run `O(n^2)` for all-equal elements. In fact, there're implementations for which it's quite difficult to construct such an example. – unkulunkulu May 16 '13 at 11:34
  • but time complexity of quicksort should be greater than merge and heap ,when all elements are same. – siddstuff May 16 '13 at 11:38
  • Im more interested in number of comparisons and time taken than storage, I have plenty of that. – clay May 16 '13 at 11:52
  • @siddstuff, no way, heapsort will build a heap, do all that stuff, while correct quicksort will not do any recursive calls when all elements are equal. It will divide the array in three parts, less than pivot, equals to pivot, greater than pivot, the first and the third of which will be empty. – unkulunkulu May 16 '13 at 11:55