A note on multipivot Quicksort

DOI10.1080/02522667.2017.1303947MaRDI QIDQ6253501zbMATH OpenFDO

Authors Vasileios Iliopoulos

Publication date 25 July 2014

Full work available at URL https://doi.org/10.1080/02522667.2017.1303947

Mathematics Subject Classification ID

Randomized algorithms (68W20) Searching and sorting (68P10)

Abstract: We analyse a generalisation of the Quicksort algorithm, where k uniformly at random chosen pivots are used for partitioning an array of n distinct keys. Specifically, the expected cost of this scheme is obtained, under the assumption of linearity of the cost needed for the partition process. The integration constants of the expected cost are computed using Vandermonde matrices.

This page was built for publication: A note on multipivot Quicksort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6253501)