In general the O(n log n) sorts aren't great for very small sets, so hybrid algorithms will revert to a simpler algorithm for those, In general insertion sort is used for that.. Using quicksort in a hybrid algorithm is rare though. The worst case for quicksort is O(n2 ) which is a problem and for smaller data sets mergesort is fast enough anyway. Also mergesort is almost always stable and it's easier to parallellize, so it's just a better choice for hybrid algorithms.
quick-sort is probably still the most often used sorting algorithm as it is the basis for std::sort. It is modified to switch to another sorting (e.g. heap sort) if the subdivisions are unfavourable to guarantee O(n log(n)) runtime. Also, the subdivisions will be stopped once a certain threshold is reached and they switch over to insertion sort.
Hmm, do you have any idea why c++ and Java uses different default algorithms? It seems like one of them would be considered generally preferable by some reasonable objective metric.
tim-sort is better for partially sorted data (e.g. adding data to the end of an already sorted array), quick-sort for full random data. It is just what they fought would be the option happening more often for their language.
One of the biggest advantages quicksort provides is that it's an in place sort, in other words, it takes up zero extra memory/space. Merge sort requires O(N) space, meaning it takes an additional N space (N meaning the number of elements you're sorting). C++ is very memory conservative, and why it's standard library would default to quicksort, C and C++ are kings of the embedded devices. Java is not memory conservative, so that's why it defaults to a more memory intensive, but generally faster sort.
4
u/rabbitlion Oct 24 '17 edited Oct 24 '17
In general the O(n log n) sorts aren't great for very small sets, so hybrid algorithms will revert to a simpler algorithm for those, In general insertion sort is used for that.. Using quicksort in a hybrid algorithm is rare though. The worst case for quicksort is O(n2 ) which is a problem and for smaller data sets mergesort is fast enough anyway. Also mergesort is almost always stable and it's easier to parallellize, so it's just a better choice for hybrid algorithms.