QuickMergeSort

QuickMergeSort applies a partition just like quicksort on the whole sequence, then applies mergesort as follows:

A new flavour of QuickMergeSort

Instead of partitioning the original sequence with a usual median-of-three pivot selection, I decided that I could use std::nth_element instead for the partition step, always choosing a pivot that splits the sequence to sort into two partitions whose sizes are respectively two thirds and one third of the size of the partition to sort. That way, it ensures that mergesort can be performerd on the biggest possible partition at each step.

QuickMergesort

QuickMergesort applies a partition just like quicksort on the whole sequence, then applies mergesort as follows:

A new flavour of QuickMergesort

Instead of partitioning the original sequence with a usual median-of-three pivot selection, I decided that I could use std::nth_element instead for the partition step, always choosing a pivot that splits the sequence to sort into two partitions whose sizes are respectively two thirds and one third of the size of the partition to sort. That way, it ensures that mergesort can be performed on the biggest possible partition at each step.

std::nth_element runs in \$\mathcal{O}(n)\$, and top-down mergesort in \$\mathcal{O}(n \log{n})\$. To be honest, I don't know whether the whole thing actually runs in \$\mathcal{O}(n \log{n})\$ or in \$\mathcal{O}(n \log^{2}{n})\$. I'd say \$\mathcal{O}(n \log{n})\$, but then again I'm not sure. Since I choose to use a top-down mergesort for the sake of simplicity, the algorithm takes \$\mathcal{O}(n \log{n})\$ space, but it could use \$\mathcal{O}(1)\$ space with a bottom-up mergesort.

std::nth_element runs in \$\mathcal{O}(n)\$, and top-down mergesort in \$\mathcal{O}(n \log{n})\$. To be honest, I don't know whether the whole thing actually runs in \$\mathcal{O}(n \log{n})\$ or in \$\mathcal{O}(n \log^{2}{n})\$. I'd say \$\mathcal{O}(n \log{n})\$, but then again I'm not sure. Since I choose to use a top-down mergesort for the sake of simplicity, the algorithm takes \$\mathcal{O}(\log{n})\$ space, but it could use \$\mathcal{O}(1)\$ space with a bottom-up mergesort.

std::nth_element runs in O(n), and top-down mergesort in \$\mathcal{O}(n * log(n))\$. To be honest, I don't know whether the whole thing actually runs in \$\mathcal{O}(n * log(n))\$ or in \$\mathcal{O}(n * log^2(n))\$. I'd say \$\mathcal{O}(n * log(n))\$, but then again I'm not sure. Since I choose to use a top-down mergesort for the sake of simplicity, the algorithm takes \$\mathcal{O}(n * log(n))\$ space, but it could use \$\mathcal{O}(1)\$ space with a bottom-up mergesort.

I think that the algorithm is quite elegant and rather fast without being too clever for its own good, and a is pretty good example of what can be done with internal buffering without being as complex as a block sort. It also allowed me to finally find a good use for std::nth_element (I was pretty disappointed by the speed of the \$\mathcal{O}(n * log(n))\$ quicksort that uses std::nth_element for its partitioning step), which is also quite nice :)

std::nth_element runs in \$\mathcal{O}(n)\$, and top-down mergesort in \$\mathcal{O}(n \log{n})\$. To be honest, I don't know whether the whole thing actually runs in \$\mathcal{O}(n \log{n})\$ or in \$\mathcal{O}(n \log^{2}{n})\$. I'd say \$\mathcal{O}(n \log{n})\$, but then again I'm not sure. Since I choose to use a top-down mergesort for the sake of simplicity, the algorithm takes \$\mathcal{O}(n \log{n})\$ space, but it could use \$\mathcal{O}(1)\$ space with a bottom-up mergesort.

I think that the algorithm is quite elegant and rather fast without being too clever for its own good, and a is pretty good example of what can be done with internal buffering without being as complex as a block sort. It also allowed me to finally find a good use for std::nth_element (I was pretty disappointed by the speed of the \$\mathcal{O}(n \log{n})\$ quicksort that uses std::nth_element for its partitioning step), which is also quite nice :)