{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T02:10:52Z","timestamp":1649124652204},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1988,12,1]],"date-time":"1988-12-01T00:00:00Z","timestamp":596937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1988,12]]},"DOI":"10.1007\/bf01954896","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T00:33:57Z","timestamp":1122856437000},"page":"764-774","source":"Crossref","is-referenced-by-count":0,"title":["On the distribution of comparisons in sorting algorithms"],"prefix":"10.1007","volume":"28","author":[{"given":"Dana","family":"Richards","sequence":"first","affiliation":[]},{"given":"Pravin","family":"Vaidya","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01954896_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi,An O(n log n) sorting network, Proc. 15th ACM Symp. Theory of Computation, 1983, pp. 1\u20139.","DOI":"10.1145\/800061.808726"},{"key":"BF01954896_CR2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(81)90031-4","volume":"13","author":"M. Atallah","year":"1981","unstructured":"M. Atallah and S. Kosaraju,An adversary-based lower bound for sorting, Info. Proc. Let., 13, 1981, pp. 55\u201357.","journal-title":"Info. Proc. Let."},{"key":"BF01954896_CR3","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(81)90005-3","volume":"12","author":"A. Borodin","year":"1981","unstructured":"A. Borodin, L. J. Guibas, N. A. Lynch, and A. C. Yao,Efficient searching using partial ordering, Info. Proc. Let., 12, 1981, pp. 71\u201375.","journal-title":"Info. Proc. Let."},{"key":"BF01954896_CR4","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/322123.322128","volume":"26","author":"F. Fussenegger","year":"1979","unstructured":"F. Fussenegger and H. Gabow,A counting approach to lower bounds for selection problems, J. ACM, 26, 1979, pp. 227\u2013238.","journal-title":"J. ACM"},{"key":"BF01954896_CR5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1002\/sapm198266191","volume":"66","author":"J. R. Griggs","year":"1982","unstructured":"J. R. Griggs,Poset measure and saturated partitions, Studies in Applied Math., 66, 1982, pp. 91\u201393.","journal-title":"Studies in Applied Math."},{"key":"BF01954896_CR6","unstructured":"D. E. Knuth,The Art of Computer Programming: Fundamental Algorithms, Addison-Wesley, 1968."},{"key":"BF01954896_CR7","unstructured":"D. E. Knuth,The Art of Computer Programming: Sorting and Searching, Addison-Wesley, 1973."},{"key":"BF01954896_CR8","unstructured":"D. S. Richards,Problems in Sorting and Graph Algorithms, UIUCDCS-R-84-1186, Ph.D. Thesis, University of Illinois, 1984."},{"key":"BF01954896_CR9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1080\/00207168408803422","volume":"16","author":"D. S. Richards","year":"1984","unstructured":"D. S. Richards,Sorting with expensive comparands, International Journal of Computer Mathematics, 16, 1984, pp. 23\u201345.","journal-title":"International Journal of Computer Mathematics"},{"key":"BF01954896_CR10","doi-asserted-by":"crossref","unstructured":"M. Saks,The information theoretic bound for problems on ordered sets and graphs, inGraphs and Orders, I. Rival (ed.), Reidel, 1985, 137\u2013168.","DOI":"10.1007\/978-94-009-5315-4_4"},{"key":"BF01954896_CR11","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1080\/00029890.1985.11971591","volume":"92","author":"H. Wilf","year":"1985","unstructured":"H. Wilf,Some examples of combinatorial averaging, Am. Math. Monthly, 92, 1985, pp. 250\u2013261.","journal-title":"Am. Math. Monthly"}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01954896.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01954896\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01954896","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T14:04:02Z","timestamp":1586354642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01954896"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["BF01954896"],"URL":"https:\/\/doi.org\/10.1007\/bf01954896","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}