{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T00:26:45Z","timestamp":1777854405895,"version":"3.51.4"},"reference-count":16,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Information Science"],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p>We present a unified treatment of a number of related inplace MSD radix sort algorithms with varying radices, collectively referred to here as 'Matesort' algorithms. These algorithms use the idea of in-place partitioning which is a considerable improvement over the traditional linked list implementation of radix sort that uses O( n) space. The binary Matesort algorithm is a recast of the classical radixexchange sort, emphasizing the role of in-place partitioning and efficient implementation of bit processing operations. This algorithm is O(k) space and has O( kn) worst-case order of running time, where k is the number of bits needed to encode an element value and n is the number of elements to be sorted. The binary Matesort algorithm is evolved into a number of other algorithms including 'continuous Matesort' for handling floating point numbers, and a number of 'general radix Matesort' algorithms. We present formulation and analysis for three different approaches (sequential, divide-and-conquer and permutation-loop) for partitioning by the general radix Matesort algorithm. The divide-andconquer approach leads to an elegantly coded algorithm with better performance than the permutation-loop-based American Flag Sort algorithm.<\/jats:p>","DOI":"10.1177\/0165551505057007","type":"journal-article","created":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T08:07:51Z","timestamp":1131610071000},"page":"467-481","source":"Crossref","is-referenced-by-count":4,"title":["Formulation and analysis of in-place MSD radix sort algorithms"],"prefix":"10.1177","volume":"31","author":[{"given":"Nasir","family":"Al-Darwish","sequence":"first","affiliation":[{"name":"ICS Department, King Fahd University of Petroleum and Minerals, Dhahran,                         Saudi Arabia"}]}],"member":"179","published-online":{"date-parts":[[2005,12,1]]},"reference":[{"key":"atypb1","volume-title":"The Art of Computer Programming \u2013 Vol. 3 Sorting and Searching","author":"D.E. Knuth","year":"1973"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/320964.320972"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/35.6.636"},{"key":"atypb6","volume-title":"Algorithms","author":"R. Sedgewick","year":"1988"},{"issue":"1","key":"atypb7","first-page":"5","volume":"6","author":"P.M. McIlroy","year":"1993","journal-title":"Computing Systems"},{"key":"atypb8","volume-title":"A Discipline of Programming","author":"E.W. Dijkstra","year":"1997"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359629"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297136"},{"key":"atypb11","volume-title":"A Comparison of Sorting Algorithms","author":"D. Rig","year":"2003"},{"key":"atypb12","volume-title":"Computer Algorithms","author":"S. Basse","year":"2000"},{"key":"atypb13","unstructured":"A. Maus, ARL \u2013 a faster in-place, cache friendly sorting algorithm.                 In: N. Stol et al. (eds), Norsk Informatik Koferranse NIK'2002, Kongsberg,                 26 November 2002 (2002) 85\u201395. Available at www.nik.no\/2002\/ (accessed 18                 July 2005)."},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"A. Al-Badaraneh and F. Al-Aker, Efficient in-place radix sorting,\n                      Informatica\n                      15(3) (2004) 295\u2013302.","DOI":"10.15388\/Informatica.2004.061"},{"key":"atypb15","volume-title":"Introduction to Algorithms: A Creative Approach","author":"U. Manber","year":"1989"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90028-5"}],"container-title":["Journal of Information Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551505057007","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551505057007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T23:07:03Z","timestamp":1777504023000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0165551505057007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":16,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1177\/0165551505057007"],"URL":"https:\/\/doi.org\/10.1177\/0165551505057007","relation":{},"ISSN":["0165-5515","1741-6485"],"issn-type":[{"value":"0165-5515","type":"print"},{"value":"1741-6485","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}