Big oh statistics for maximum moves of new patented sorting algorithm better than heap sort

From: <posting_at_comp.databases>
Date: 1999/08/06
Message-ID: <37fa1d37.2336235529_at_news.alt.net>#1/1


From posting_at_sci.math.research:  

>
> 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.

The maximum number of moves is N * ( ( b - 1)/2).

The maximum number of moves with rewrite of the sorted list is:

        N * ( ( b - 1)/2) + ( INT( N / b) * b)

where b is the number of blanks used.

In contrast to a heap sort (the best performer for number of moves at n lg n), for b = 11, the above algorithm has over 40% fewer moves. Received on Fri Aug 06 1999 - 00:00:00 CEST

Original text of this message