Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
The length of a sorted sequence produced by the internal sort phase of a large scale general purpose sort routine is a random variable. In a random access environment, any given set of such sequences can be merged in an optimal way, and in practice this is often done. The expected work per item required by an optimal merge depends upon the probability distribution for sequence length, and it is this dependence which is studied in this paper. Reasonably sharp upper and lower bounds are derived. The distribution which is optimal in the sense of minimizing the lower bound on any bounded interval is determined, and it is shown that this is the strongest result of its kind. © 1972, ACM. All rights reserved.
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Xiaoxiao Guo, Shiyu Chang, et al.
AAAI 2019
Michael Muller, Anna Kantosalo, et al.
CHI 2024
Fahiem Bacchus, Joseph Y. Halpern, et al.
IJCAI 1995