刹那式(Setsuna-Shiki)

Setsuna-Shiki is a new method of differential sorting algorithm that applies bisection insertion sorting.
For a sorted array, focus on the place where the value change is made and sort very fast.

It has the following features.

• Comparison sort
• Stable sort
• External area: None
• Average time: O (log N)
• Worst time: O (log N)
• Best time: O (2)
• Recursion: None

Source Code

Setsuna-Shiki(MIT License)

Basic algorithm

• Change the value at any position in the sorted array.
• If (Changed position value < value below change position), the lower range is binary-searched and rotate from change position to search position.
• If (value above change position < Changed position value), the upper range is binary-searched and rotate from change position to search position.

Examples

Change the value at any position in the sorted array.
0 1 2 4 5 6 7 9|Sorted array
        ↓
0 1 2 4 x 6 7 9|Change the value at any position

If (Changed position value < value below change position), the lower range is binary-searched and rotate from change position to search position.
0 1 2 4 5 3 7 9|In the case of [5]=3
0 1 2 4 5|. . .|Binary search the lower range
. . .|3 4 5|. .|Rotate from change position to search position
0 1 2 3 4 5 7 9|Sort result

If (value above change position < Changed position value), the upper range is binary-searched and rotate from change position to search position.
0 1 8 4 5 6 7 9|In the case of [2]=8
. . .|4 5 6 7 9|Binary search the upper range
. .|4 5 6 7 8|.|Rotate from change position to search position
0 1 4 5 6 7 8 9|Sort result

.

Points devised

Even if binary search is performed to the area where the same value is continuous, stability is maintained.

• The binary search in the lower range searches the end of the continuous area.
• The binary search in the upper range searches the beginning of a continuous area.

Build & Test

The following environment has been verified.

• Windows 10 Pro 64bit
• Core i7-8700 3.20 GHz

Msvc

Microsoft(R) C/C++ Optimizing Compiler Version 19.15.26732.1 for x64
Microsoft (R) Incremental Linker Version 14.15.26732.1

cl Main.cpp -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe

clang++

clang version 7.0.0 (tags/RELEASE_700/final)
Target: x86_64-w64-windows-gnu

clang++ Main.cpp -O3 -o TestClang++.exe
TestClang++.exe

g++

gcc version 8.2.0 (Rev3, Built by MSYS2 project)
Target: x86_64-w64-mingw32

g++ Main.cpp -O3 -o TestG++.exe
TestG++.exe

.

Average benchmark

The following is the case of changing the random position of the sorted array to a random value.
The unit is seconds, the lower the number, the faster.

Msvc

clang++

g++

Limited condition benchmark

The following is sorted by the array [100,000,000].
The unit is seconds, the lower the number, the faster.

Worst case 1

When changing the first to the maximum value for a sorted array.

Worst case 2

When changing the end to the minimum value for a sorted array.

Best case

When the position is specified randomly without changing the value for the sorted array.

Finally

How was it?

We came up with the idea of ​​differential sorting, in terms of the fact that sorting does not always have to be done in its entirety.
Although the comparison between std::sort and std::stable_sort, which is an overall sort, and Setsuna-Shiki, which is an diff sort, is not fair, it should be used to determine the usefulness of diff sort.

If you operate well, you can get a rapid performance, but if you use it incorrectly it will be a two-edged sword.

The sort algorithm is still romantic.

Thanks for watching!