why we are always using quick sort ? or any specific sorting algorithm?

Question

why we are always using quick sort ? or any specific sorting algorithm ??

i tried some experiment on my PC using quick,merge,heap,flash sort

results:-

sorting algorithm : time in nanosecond -> time in minutes

quick sort time : 135057597441 -> 2.25095995735

Flash sort time : 137704213630 -> 2.29507022716667

merge sort time : 138317794813 -> 2.30529658021667

heap sort time : 148662032992 -> 2.47770054986667

using java in built function

long startTime = System.nanoTime();

given times are in nanoseconds there hardly any difference between them if we convert them into seconds for 20000000 random integer data and max array size is 2147483647 in java.if we are using in-place algorithm then there may be difference of 1 to 2 min till max array size.

if the difference is too small why we should care ??

Answer 1

All of the algorithms presented have a similar average case bounds, of O(n lg n), which is the "best" a comparison sort can do.

Since they share the same average bounds, the expected performance of these algorithms over random data should be similar - which is what the findings show. However, the devil is in the details. Here is a very quick summary; follow the links for further details.

Quicksort is generally not stable (but there are stable variations). While quicksort has an average bounds of O(n lg n), Quicksort has a worst case bounds of O(n * n) but there are ways to mitigate this. Quicksort, like heapsort, is done in-place.

Merge-sort is a stable sort. Mergesort has a worst case bounds of O(n lg n) which means it has predictable performance. Base merge-sort requires O(n) extra space so it's generally not an in-place sort (although there is an in-place variant, and the memory for a linked list implementation is constant).

Heapsort is not stable; it also has the worst case bounds of O(n lg n), but has the benefit of a constant size bounds and being in-place. It has worse cache and parallelism aspects than merge-sort.

Exactly which one is "best" depends upon the use-case, data, and exact implementation/variant.

---

Merge-sort (or hybrid such as Timsort) is the "default" sort implementation in many libraries/languages. A common Quicksort-based hybrid, Introsort is used in several C++ implementations. Vanilla/plain Quicksort implementations, should they be provided, are usually secondary implementations.

Merge-sort: a stable sort with consistent performance and acceptable memory bounds.

Quicksort/heapsort: trivially work in-place and [effectively] don't require additional memory.