Browse Prior Art Database

A pre-sorting method for efficient sorting

IP.com Disclosure Number: IPCOM000250421D
Publication Date: 2017-Jul-13
Document File: 1 page(s) / 47K

Publishing Venue

The IP.com Prior Art Database

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 82% of the total text.

A pre-sorting method for efficient sorting

This method is based on the observation that in sorting a set of elements one can optimize the number of necessary comparisons by dynamically constructing ordered layers of sorted elements (or pointers to the elements for memory efficiency) which are later merged with reduced number of comparisons. In this procedure each element or its corresponding index or pointer is placed into specific layer by performing maximum two comparisons with leftmost (minimum) element in the layer, and the rightmost (maximum) element in the layer. As a result, all elements are distributed across layers and in each layer elements are sorted.

This method provides an efficient sorting procedure which can significantly reduce sorting time especially in large data sets. We envision the following advantages with our method:

- Increased speed (although not trivial to formally prove, in many practical situations the complexity << O(Nlog2N))

- Memory efficiency (operating in index/pointer space to avoid creating copies of large objects) -

Input: set S = {e1,…,eN} of N, N>=2 data elements and a comparison rule Comp(ei,ej) -> {<,>,=} defined for any pair of elements from S.

The algorithm proceeds in the following steps:

1. Set i=1. Initialize L1 = {e1}, M=1 2. If e1>e2, then set L1={e2, e1}, otherwise set L1={e1, e2} 3. FOR i=3,…,N

a. Flag = TRUE, j=1 b. WHILE(Flag AND j<=M)

i. IF First_Elem(Lj)>=ei THEN Lj = {ej,Lj}, FLAG = FALSE EXIT WHILE ii. IF Last_Elem(Lj)<=...