+ 3

Why there's no quicksort and mergesort as a hybrid-sorting algorithm? Is it not possible?

From my perception and experience, Lomuto's is slower than Hoare's, and quicksort that uses it's median as the pivot seems faster. The best case of it is the same as mergesort's average case which the array recursively evenly divided by 2. I tried to make my own hybrid-sorting algorithm that combines the concept of quicksort by median and mergesort since I never found one. I'm not questioning the code, my question is, is it not actually possible to combine quick and merge sort? Edit: Thanks to Schindlabua, I just realized my question is not detailed enough. The quicksort that I'm imagine is where you take the middle index as the pivot. From 0 to m, increment until it gets a number higher than the pivot, decrement until it gets a number lower than the pivot from n-1 to m. After that, swap them, and then recursively split them into 2 subarrays, do the same thing again and so on.

17th Oct 2020, 4:41 AM
LastSecond959
LastSecond959 - avatar
3 odpowiedzi
+ 4
Splitting a large chunk of data into parts, sorting each part with e.g. quicksort, and merging the results with the merge part of mergesort is not uncommon, that way you can offload the subarrays to different machines or threads and split the workload. I'm not sure if what you are proposing is similar.
17th Oct 2020, 10:54 AM
Schindlabua
Schindlabua - avatar
+ 3
Sounds interesting :) Code it up and lets run some tests!
18th Oct 2020, 10:44 PM
Schindlabua
Schindlabua - avatar
0
Schindlabua I updated the question, added more details, hopefully you get my point.
18th Oct 2020, 10:22 AM
LastSecond959
LastSecond959 - avatar