<p><a href="https://www.wild-inter.net/" rel="nofollow noreferrer">Sebastian Wyld</a> from the <a href="https://www.liverpool.ac.uk/computer-science/staff/sebastian-wild/" rel="nofollow noreferrer">University of Liverpool</a> has been extensively working on the analysis of various versions of QuickSort: His 2016 thesis, &quot;<a href="https://www.semanticscholar.org/paper/Dual-Pivot-Quicksort-and-Beyond%3A-Analysis-of-and-Wild/06a57d5440d8f2e7cfc3de0eafbfded6e947b912" rel="nofollow noreferrer">Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential</a>&quot;, explored the analysis of the complexity of &quot;Multiway Quicksort, i.e., partitioning the input in one step around several pivots&quot; and includes</p>
<ul>
<li>an extensive survey of such variants,</li>
<li>an average case analysis of the generic one in terms of both
<ul>
<li>the number of comparisons and</li>
<li>the number of accesses to external memory, and</li>
</ul>
</li>
<li>some <a href="https://doi.org/10.1145/2629340" rel="nofollow noreferrer">intricate results about the case where keys can be repeated</a>.</li>
</ul>
<p>Sebastian is very kind, and if you have questions about his work (after studying it seriously), I do believe that he would answer any question you may have.</p>
<p>I hope it helps!</p>

CC BY-SA 4.0
2022-11-19T10:11:01.713Z
2022-11-19T10:11:01.713Z
J.y B.y
<p>I'm studying a variation of Quicksort in which the algorithm samples a subarray of size <span class="math-container">$f(n)&lt; n$</span> (<span class="math-container">$n$</span> is the size of the input array) and then chooses the pivot from this subarray. The pivot is accepted if it lies in the middle third of the sampled array, otherwise it is rejected and the subarray is sampled again until the pivot is accepted. Is there any reference in which this variation has been studied?</p>

CC BY-SA 4.0
2022-11-21T10:18:14.577Z
If you sample a subarray, it does not make much sense to "just" choose a single pivot and divide the array in two parts according to this single pivot. Rather, you can take advantage of the elements accessed to partition the array into $f(n)+1$ blocks by 1) sorting the $f(n)$ elements) and partition the $n$ elements according to those.
J.y B.y
<sorting>
Sampling strategies for Quicksort
joeren1020
# Sampling strategies for Quicksort

(Asked by: username_0 on 2022-11-19)

I'm studying a variation of Quicksort in which the algorithm samples a subarray of size $f(n)< n$ ($n$ is the size of the input array) and then chooses the pivot from this subarray. The pivot is accepted if it lies in the middle third of the sampled array, otherwise it is rejected and the subarray is sampled again until the pivot is accepted. Is there any reference in which this variation has been studied?

**Tags:** sorting

> **Comments:**
> **username_1**: If you sample a subarray, it does not make much sense to "just" choose a single pivot and divide the array in two parts according to this single pivot. Rather, you can take advantage of the elements accessed to partition the array into $f(n)+1$ blocks by 1) sorting the $f(n)$ elements) and partition the $n$ elements according to those.  

---

## 1 answers

### Answer by username_1 on 2022-11-19. Score: 1

[Sebastian Wyld](https://www.wild-inter.net/) from the [University of Liverpool](https://www.liverpool.ac.uk/computer-science/staff/sebastian-wild/) has been extensively working on the analysis of various versions of QuickSort: His 2016 thesis, "[Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential](https://www.semanticscholar.org/paper/Dual-Pivot-Quicksort-and-Beyond%3A-Analysis-of-and-Wild/06a57d5440d8f2e7cfc3de0eafbfded6e947b912)", explored the analysis of the complexity of "Multiway Quicksort, i.e., partitioning the input in one step around several pivots" and includes

* an extensive survey of such variants,
* an average case analysis of the generic one in terms of both
  + the number of comparisons and
  + the number of accesses to external memory, and
* some [intricate results about the case where keys can be repeated](https://doi.org/10.1145/2629340).

Sebastian is very kind, and if you have questions about his work (after studying it seriously), I do believe that he would answer any question you may have.

I hope it helps!


---

