NewBlock sort – фундаментальный алгоритм сортировки со сложностью O(n*log(n/2))

Welcome! Run-Time Systems

to main

NewBlock sort is a fundamental sorting algorithm with complexity O ( n * log ( n /2))

Sorting is one of the fundamental software algorithms. Much has been invented in thisdirection, but no optimal

solutions have been found, the complexity of the solutions and the speed of data processing leave much to be desired.

All algorithms have been described many times and published in special publications and on the Internet .

Brief comparison information on commonly used data sorting algorithms is given in Table 1.

This article discusses a completely different algorithm, simpler and more effective - block

( NewBlock sort ), with complexity:

best ( min ) – O (( n /2)* log ( n )) and

worst (max) – O(n*log(n/2)),

ratio max / min = 2*(1-1/ log ( n )) and always known number of passes when sorting = log ( n ) .

The entire array of records (numbers) is represented in the form of blocks and semi-blocks:

On the first pass, the block size is 2, half-block is 1

On the second pass the block size is 4, half block size is 2

On the third pass, the block size is 8, half-block is 4

On the fourth pass, the block size is 16, half-block is 8

etc., i.e. the block size is always 2 to the power of the pass number

For example, if the number of records is 64, you need to run

log (64) = 6 passes and compare:

at best ( n /2)* log ( n ) = (64/2)* log (64) = 192 records (numbers)

worst case n * log ( n /2) = 64 * log (64/2) = 320 records (numbers).

For a more complete understanding of the algorithm NewBlock sort

Fig.1, Fig.2 and Fig.3 show array sorting

of 16 numbers.

--- Comparison operations are shown in black.

--- Transfer operations are shown in red

after comparison.

--- Transfer operations are shown in blue

no comparison.

For an odd pass, data from array 1 is transferred to array 2, and for an even pass, from array 2 to array 1. .

Now about memory usage:

If arrays of numbers are sorted, then additional memory will be required in the amount of n -

the initial size of the array.

If records are sorted, then additional memory will be required 2n for pointers.

NewBlock sort algorithm is simply perfect for working in multi-threaded execution on multi-cores

processors, allowing the next sorting pass to be started without waiting for the previous pass to complete,

which significantly reduces sorting time.

Large arrays of records (numbers) can be sorted by dividing them into smaller parts on computers on the network,

which further reduces sorting time.

The NewBlock sort algorithm is practically implemented in the C language in the Start-RTS+ RDBMS, a cross-platform system relational database management for use in applications running

without any code changes in the environment of 64-bit operating systems MX - Linux and Windows .

Based on Start - RTS +, an applied technological system Smeta- RTS has been developed for calculating estimates in the area

construction with the regulatory frameworks of the regions of Russia.

e-mail:rts@rtsrts.com