{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:04Z","timestamp":1750308124456,"version":"3.41.0"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,6,1]],"date-time":"2005-06-01T00:00:00Z","timestamp":1117584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCSE Bull."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>\n            This paper discusses a possible student project for use within the Data Structures and Algorithms treatment of linked lists. Students can explicitly compare the recursive list-oriented MergeSort algorithm with iterative list-oriented MergeSort algorithms (with O(\n            <jats:italic>n<\/jats:italic>\n            ) space overhead) including the \"Natural MergeSort.\" The author's experimental results are shown for implementations in C and in Java.\n          <\/jats:p>","DOI":"10.1145\/1083431.1083461","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T19:28:32Z","timestamp":1131391712000},"page":"46-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["List processing"],"prefix":"10.1145","volume":"37","author":[{"given":"Timothy J.","family":"Rolfe","sequence":"first","affiliation":[{"name":"Eastern Washington University, Cheney, Washington"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"volume-title":"Wesley","year":"1998","author":"Sedgewick Robert","key":"e_1_2_1_1_1"},{"volume-title":"Wesley","year":"2003","author":"Sedgewick Robert","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"Sahni Sartaj. Data Structures Algorithms and Applications in C++. McGraw-Hill 1998.   Sahni Sartaj. Data Structures Algorithms and Applications in C++. McGraw-Hill 1998."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90088-Q"},{"key":"e_1_2_1_5_1","unstructured":"Knuth Donald. The Art of Computer Programming; Volume 3: Sorting and Searching. Second edition: Addison-Wesley 1998.   Knuth Donald. The Art of Computer Programming; Volume 3: Sorting and Searching. Second edition: Addison-Wesley 1998."},{"key":"e_1_2_1_6_1","unstructured":"Proof provided by Dr. Ray Hamel of my department: There are on average (n-1)\/2 sequence breaks in a sequence of n randomly selected distinct items. Each sequence S of n items {where S = (S1 . . . Sn)} has its reverse sequence R such that Rj = Sn-j+1. Both sequences together have n-1 sequence breaks: for each adjacent pair of (distinct) values the two values are out of order either in R or in S (but not in both) and there are n-1 adjacent pairs. For randomly selected sequences both sets are equally likely so that there are (n-1)\/2 sequence breaks on average.  Proof provided by Dr. Ray Hamel of my department: There are on average (n-1)\/2 sequence breaks in a sequence of n randomly selected distinct items. Each sequence S of n items {where S = (S1 . . . Sn)} has its reverse sequence R such that Rj = Sn-j+1. Both sequences together have n-1 sequence breaks: for each adjacent pair of (distinct) values the two values are out of order either in R or in S (but not in both) and there are n-1 adjacent pairs. For randomly selected sequences both sets are equally likely so that there are (n-1)\/2 sequence breaks on average."},{"issue":"1","key":"e_1_2_1_7_1","first-page":"113","volume":"25","author":"Rolfe Timothy","year":"2000","journal-title":"Dr. Dobb's Journal"}],"container-title":["ACM SIGCSE Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1083431.1083461","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1083431.1083461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:23Z","timestamp":1750262903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1083431.1083461"}},"subtitle":["sort again, naturally"],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":7,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1083431.1083461"],"URL":"https:\/\/doi.org\/10.1145\/1083431.1083461","relation":{},"ISSN":["0097-8418"],"issn-type":[{"type":"print","value":"0097-8418"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}