On the distribution of comparisons in sorting algorithms
type: Item
instance of: scholarly article
title: On the distribution of comparisons in sorting algorithms
zbMATH Open document ID: 0663.68078
DOI: 10.1007/BF01954896
author: Pravin M. Vaidya
author: Dana Richards
published in: BIT
publication date: 1988-01-01T00:00:00Z
review text: We consider the following natural conjecture: For every sorting algorithm every key will be involved in \(\Omega\) (log n) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involve \(n-n^{\epsilon}/2+1\) keys in at least \(\epsilon\) \(log_ 2 n\) comparisons, \(\epsilon >0\). Further, there exists a sorting algorithm that will for every input involve at most \(n-n^{\epsilon /c}\) keys in greater than \(\epsilon\) \(log_ 2 n\) comparisons, where c is a constant and \(\epsilon >0\). The conjecture is shown to hold for ``natural'' algorithms from the literature.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4085044
zbMATH Keywords: adversaries
zbMATH Keywords: sorting
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
cites work: Sorting in \(c \log n\) parallel steps
cites work: An adversary-based lower bound for sorting
cites work: Efficient searching using partial ordering
cites work: A Counting Approach to Lower Bounds for Selection Problems
cites work: Poset Measure and Saturated Partitions
cites work: Q5585020
cites work: Q4057549
cites work: Sorting with expensive comparands
cites work: Some Examples of Combinatorial Averaging
full work available at URL: https://doi.org/10.1007/bf01954896
OpenAlex ID: W1969935217
description: scientific article; zbMATH DE number 4085044