Big-oh statistics for number of comparisons and run time of new patented sorting algorithm
A poster described US Patent 5,926,815 ("Binary Sort Access Method and Apparatus"), which keeps data physically sorted by leaving eleven blank slots between items, using binary search plus insertion to place new keys and rewriting the whole list with fresh gaps when a gap group fills. He asked for Big-O figures for worst-case comparisons and average/worst run time. Responses were dismissive ("just trading memory for speed", "an old, primitive idea") or off-topic, and Jonathan Leffler only identified the inventor, Colin James III. No Big-O analysis or resolution was recorded.
Auto-generated by DrWatson from the posts below — may be imperfect; read the full thread.
From the abstract of US Patent 5,926,815, issued July 20, 1999, "BINARY SORT ACCESS METHOD AND APPARATUS": "The binary sort access method and apparatus makes use of a binary search to show where an item of data not found should be placed in sorted order within a list in a table in memory or in a file ... When no blank table entry is available items of data are moved to make room for the next succeeding item of data. A partially filled or filled list of items may be rewritten again to provide one or more blank table entries between each item of data." From the detailed description of the invention: 1. The apparatus keeps data items in physically sorted order. 2. To avoid (or delay) moving on average n/2 items whenever an item is inserted in sorted order into the list, sorted items initially have eleven blank spaces inserted between each item, making the space required as n + 11 * n or 12 * n. 3. When the particular group of eleven empty or partially filled blanks is determined, the new item is put there with a straight insertion sort. 4. Whenever an area of eleven originally blank items is filled up with physically sorted items, the entire list is rewritten with eleven blanks again interspersed between each physically sorted data item. What are the Big-oh statistics of this sort for: 1. Worst (maximum) number of comparisons; and 2. Average run time and worst (maximum) run time. No one has come up with any meaningful statistics, possibly because no one really has taken the time to understand fully how the sort works.
From Thomas Jäckel <jaeckel@netcologne.de>: > > > posting@usenet.groups schrieb: > > > ..... > > What are the Big-oh statistics of this sort for: > > > > 1. Worst (maximum) number of comparisons; and > > 2. Average run time and worst (maximum) run time. > > > > No one has come up with any meaningful statistics, > > possibly because no one really has taken the time to > > understand fully how the sort works. > > Take more memory and you can fasten the sort, that's all. > > Thomas Nonsense. Obviously it's supposed to be an external sort, ie, disk to disk, for millions of keys
posting@usenet.groups schrieb: > ..... > What are the Big-oh statistics of this sort for: > > 1. Worst (maximum) number of comparisons; and > 2. Average run time and worst (maximum) run time. > > No one has come up with any meaningful statistics, > possibly because no one really has taken the time to > understand fully how the sort works. Take more memory and you can fasten the sort, that's all. Thomas
It's patented, so it has something unique that no other sort does. Now it's a matter of how well it works in the various application environments and it's acceptance by the user community. Who has the patent? posting@usenet.groups wrote: > > From the abstract of US Patent 5,926,815, issued > July 20, 1999, "BINARY SORT ACCESS METHOD AND > APPARATUS": > > "The binary sort access method and apparatus makes > use of a binary search to show where an item of data > not found should be placed in sorted order within a > list in a table in memory or in a file ... When no > blank table entry is available items of data are > moved to make room for the next succeeding item of > data. A partially filled or filled list of items > may be rewritten again to provide one or more blank > table entries between each item of data." > > From the detailed description of the invention: > > 1. The apparatus keeps data items in physically > sorted order. > > 2. To avoid (or delay) moving on average n/2 items > whenever an item is inserted in sorted order into > the list, sorted items initially have eleven blank > spaces inserted between each item, making the space > required as n + 11 * n or 12 * n. > > 3. When the particular group of eleven empty or > partially filled blanks is determined, the new item > is put there with a straight insertion sort. > > 4. Whenever an area of eleven originally blank > items is filled up with physically sorted items, the > entire list is rewritten with eleven blanks again > interspersed between each physically sorted data > item. > > What are the Big-oh statistics of this sort for: > > 1. Worst (maximum) number of comparisons; and > 2. Average run time and worst (maximum) run time. > > No one has come up with any meaningful statistics, > possibly because no one really has taken the time to > understand fully how the sort works.
posting@usenet.groups schrieb: > From Thomas Jäckel <jaeckel@netcologne.de>: > > > > > > > posting@usenet.groups schrieb: > > > > > ..... > > > What are the Big-oh statistics of this sort for: > > > > > > 1. Worst (maximum) number of comparisons; and > > > 2. Average run time and worst (maximum) run > time. > > > > > > No one has come up with any meaningful > statistics, > > > possibly because no one really has taken the > time to > > > understand fully how the sort works. > > > > Take more memory and you can fasten the sort, > that's all. > > > > Thomas > > Nonsense. Obviously it's supposed to be an external > sort, ie, disk to disk, for millions of keys So what? Millions of keys, disk to disk says nothing. It is a problem of technologie and perhabs limited resources. The idea of the algorithm my be suitable for this special case, but that changes nothing. It is an old and primitive idea perhabs optimized for a certain situation or problem. Tell me more about the algorithm, if you want to convince me. Thomas
Charlie Briney wrote: > It's patented, so it has something unique that no other sort does. Now it's > a matter of how well it works in the various application environments and > it's acceptance by the user community. > > Who has the patent? > > posting@usenet.groups wrote: > > From the abstract of US Patent 5,926,815, issued > > July 20, 1999, "BINARY SORT ACCESS METHOD AND > > APPARATUS": According to the US Patent and Trademarks Office (http://www.uspto.gov/patft), the inventor is: James, III; J. Colin (1613 Morning Dr., Loveland CO 80538-4410). There used to be a newsgroup, alt.bonehead.colin-james-iii, dedicated to this gentleman (circa 1996?). You can also find some information by searching Yahoo with the term 'Colin James III'; that leads you to the right place immediately. He used to have a web site with some interesting material on it; I don't have the URL in my records, I regret to say. Seek there before enquiring further. -- Yours, Jonathan Leffler (jleffler@informix.com) #include Guardian of DBD::Informix v0.60 (v0.61_02) -- http://www.perl.com/CPAN Informix IDN for D4GL & Linux -- http://www.informix.com/idn