Re: Big-oh statistics for number of comparisons and run time of new patented sorting algorithm

Oh da%$. I knew I should have patented my UnShuffle Sort Algorithm. Now on that I DO have BigO calculations. Order is O(kN) where k is a measure of the entropy in the original data. K=1 represents an already sorted input and the order of sort is indeed N (actually performing N-1 comparisons and no swaps).

Ahh but I digress....

Art S. Kagel

Inventor of the UnShuffle Sort Algorithm, published 1985.

posting_at_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.
Received on Thu Jul 29 1999 - 00:00:00 CEST