Time Lower Bounds for Sorting Roughly Sorted Sequences

Yoshihide ITARASHI, Juha KORTELAINEN

Summary :

A sequence α(a₁, , a_n) is k-sorted if for all 1i, jn, i jk implies a_ia_j. The number of k-sorted permutations of {1, , n} is denoted by R_k(n). We show that 1.4439n and 1.6933n are average case lower bounds on the numbers of comparisons needed to sort 3-sorted and 4-sorted sequences of length n, respectively. A compact form of a characteristic equation of degree k1 for a lower bound on R_k (n)/R_k(n1) is derived. From this characteristic equation, we also derive a good lower bound on the expected number of comparisons needed to sort k-sorted sequences for each k5.

• Publication: IEICE TRANSACTIONS on transactions Vol.E73-E No.11 pp.1893-1898
• Publication Date: 1990/11/25
• Type of Manuscript: PAPER
• Category: Algorithm and Computational Complexity

Authors

Yoshihide ITARASHI
Juha KORTELAINEN

Keyword