3

basically i saw i video on youtube that visualized sorting algorithms and they provided the program so that we can play with it .. and the program counts two main things (comparisons , array accesses) .. i wanted to see which one of (merge & quick) sort is the fastest ..

for 100 random numbers

quick sort:
comparisons 1000
array accesses 1400

merge sort:
comparisons 540
array accesses 1900

so quick sort uses less array access while merge sort uses less comparisons and the difference increases with the number of the indexes .. so which one of those is harder for computer to do?

Hunar
  • 67
  • 7
  • Benchmark it. By the way, which video did you see? – Nayuki May 05 '16 at 20:39
  • Possible duplicate of [Why is quicksort better than mergesort?](http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort) – random May 05 '16 at 20:41
  • What language is this? Agnostic? – Laurel May 05 '16 at 20:42
  • You can try do it with 10000000 random numbers and then just check your cpu in the task manager and compare the cpu. – The scion May 05 '16 at 20:42
  • i forgot what video was it but the program and source code they made is here http://panthema.net/2013/sound-of-sorting/ it's made with c++ .. it can only sort up to 2048 – Hunar May 05 '16 at 20:49

2 Answers2

1

The numbers are off. Results from actual runs with 100 random numbers. Note that quick sort compare count is affected by the implementation, Hoare uses less compares than Lomuto.

quick sort (Hoare partition scheme)

pivot reads      87   (average)
compares        401   (average)
array accesses  854   (average)

merge sort:

compares        307  (average)
array accesses 1400  (best, average, worst)

Since numbers are being sorted, I'm assuming they fit in registers, which reduces the array accesses.

For quick sort, the compares are done versus a pivot value, which should be read just once per recursive instance of quick sort and placed in a register, then one read for each value compared. An optimizing compiler may keep the values used for compare in registers so that swaps already have the two values in registers and only need to do two writes.

For merge sort, the compares add almost zero overhead to the array accesses, since the compared values will be read into registers, compared, then written from the registers instead of reading from memory again.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
1

Sorting performance depends on many conditions, I think answering your exact question won't lead to a helpful answer (you can benchmark it easily yourself).

  1. Sorting a small number of elements is usually not time critical, benchmarking makes sense for larger lists.
  2. Also it is a rare case to sort an array of integers, it is much more common to sort a list of objects, comparing one or more of their properties.
  3. If you head for performance, think about multi threading.
  4. MergeSort is stable (equal elements keep their relative position), QuickSort is not, so you are comparing different results.

In your example, the quicksort algorithm is probably faster most of the time. If the comparison is more complex, e.g. string instead of int or multiple fields, MergeSort will become more and more effective because it needs fewer (expensive) comparisons. If you want to parallize the sorting, MergeSort is predestined because of the algorithm itself.

martinstoeckli
  • 23,430
  • 6
  • 56
  • 87