eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/7479
Title:  Sorting and Searching Using Controlled Density Arrays 
Authors:  Melville, Robert C. Gries, David 
Keywords:  computer science technical report 
Issue Date:  Dec1978 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR78362 
Abstract:  Algorithms like insertion sort run slowly because of costly shifting of array elements when a value is inserted or deleted. The amount of shifting, however, can be reduced by leaving gaps  unused array locations into which new values can be inserted  at regular intervals in the array. The proper arrangement of gaps is maintained by periodic adjustment. We demonstrate this technique with a stable comparison sort algorithm with expected time $O(N \log N)$, worst case time $O(N \sqrt{N})$, and space requirements 2N. We conjecture that, by using an interpolation search, the expected time can be reduced to $O(N \log \log N)$. By comparison, Quicksort takes expected time $O(N \log N)$, worst case time $O(N^{2})$ and space $N + \log N$. Second, we show that for any fixed $d \geq 2$ a table management algorithm can be constructed that can process a sequence of $N$ instructions chosen from among INSERT, DELETE, SEARCH, and, MIN in worst case time $O(N^{1+1/d})$. Experiments with a version of the algorithms using $d=2$ show a marked improvement over balanced tree schemes for $N$ as large as several thousand. 
URI:  http://hdl.handle.net/1813/7479 
Appears in Collections:  Computer Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
