Volume 11, Issue 4 (2-2026)
mmr 2026, 11(4): 45-56 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Imany Nabiyyi R, Javanian M. Median Quicksort Process. mmr 2026; 11 (4) :45-56
URL: http://mmr.khu.ac.ir/article-1-3434-en.html
URL: http://mmr.khu.ac.ir/article-1-3434-en.html
1- University of Tabriz , imany@tabrizu.ac.ir
2- University of Zanjan
2- University of Zanjan
Abstract: (157 Views)
The Quicksort algorithm sorts the data stored in an array. The Partial Quicksort algorithm sorts the l 
smallest numbers out of numbers stored in an array of length n 
. The Quicksort on the fly provides online first the smallest, then the second smallest and so on. If we stop at the l Y n l n 
, a correctly normalized version of the number of comparisons needed to sort the l n l ≔ nt 
، t ∈ 0,1 
and n →∞ 
, then the process Y n t ≔ Y n nt n 
converges to Y t 
in the space of cadlag functions.
smallest numbers out of numbers stored in an array of length . The Quicksort on the fly provides online first the smallest, then the second smallest and so on. If we stop at the -th smallest, we obtain Partial Quicksort. In this paper, we analyze , a correctly normalized version of the number of comparisons needed to sort the smallest numbers out of numbers stored in an array of length , by the Median Quicksort algorithm. We show that whenever ، and , then the process converges to in the space of cadlag functions.
Keywords: Median Quicksort algorithm, weighted branching process, contraction method, space of cadlag function.
Type of Study: S |
Subject:
Stat
Received: 2024/12/7 | Revised: 2026/02/26 | Accepted: 2025/11/2 | Published: 2026/02/26 | ePublished: 2026/02/26
Received: 2024/12/7 | Revised: 2026/02/26 | Accepted: 2025/11/2 | Published: 2026/02/26 | ePublished: 2026/02/26
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
