# Sortingalgorithm.hayateshiki

Hayate-Shiki is an improved merge sort algorithm with the goal of "faster than quick sort".
Alternatives To Sortingalgorithm.hayateshiki
Javascript Algorithms170,41925 days ago4June 02, 2018311mitJavaScript
📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
Python159,187
13 hours ago176mitPython
All Algorithms implemented in Python
Java52,108
19 hours ago4mitJava
All Algorithms implemented in Java
Javascript26,623
6 days ago39gpl-3.0JavaScript
Algorithms and Data Structures implemented in JavaScript for beginners, following best practices.
C Plus Plus24,534
12 hours ago33mitC++
Collection of various algorithms in mathematics, machine learning, computer science and physics implemented in C++ for educational purposes.
Algorithms22,51214125 days ago5October 04, 2020200mitPython
Minimal examples of data structures and algorithms in Python
C16,291
a day ago19gpl-3.0C
Collection of various algorithms in mathematics, machine learning, computer science, physics, etc implemented in C for educational purposes.
Tech Interview For Developer10,689
9 days ago2mitJava
👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖
Algoxy5,709
19 hours agoTeX
Book of Elementary Algorithms and Data structures
Algorithms4,760
3 months ago105mitC++
Algorithms & Data structures in C++.
Alternatives To Sortingalgorithm.hayateshiki
Select To Compare

Alternative Project Comparisons

# 颯式(Hayate-Shiki)

Hayate-Shiki is an improved merge sort algorithm with the goal of "faster than quick sort".

It has the following features.

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

# Basic algorithm

• The external area is regarded as a 2N continuous band.
• The following rules apply when placing values ​​in the external area.
• If (maximum <= value), place it above the ascending order column and update the maximum.
• If (value < minimum), place it below the descending column and update the minimum.
• If (minimum <= value < maximum), place new values ​​(maximum and minimum) in ascending order column, and let the value group arranged so far be Part.
• Merge parts.

## Examples

``````The external area is regarded as a 2N continuous band.

4 5 1 2 7 6 3 8|Input column
. . . . . . . .|External area
->Asc     Dsc<-|Actually

|4 5 1 2 7 6 3 8|Input column
. . . . . . . . . . . . . . . .|External area
Dsc<-|->Asc          |2N continuous band
``````
``````Put new values ​​(maximum and minimum) in ascending order column.
|. 5 1 2 7 6 3 8
. . . . . . . . 4 . . . . . . .
``````
``````The next value is (maximum <= value), place it above the ascending order column and update the maximum.
|. . 1 2 7 6 3 8
. . . . . . . . 4 5 . . . . . .
``````
``````The next value is (value < minimum), place it below the descending column and update the minimum.
|. . . 2 7 6 3 8
. . . . . . . 1 4 5 . . . . . .
``````
``````The next value is (minimum <= value < maximum), place new values ​​(maximum and minimum) in ascending order column,
and let the value group arranged so far be Part.(Part: 145 completed)
|. . . . 7 6 3 8
. . . . . . .|1 4 5|2 . . . . .
``````
``````The next value is (maximum <= value), place it above the ascending order column and update the maximum.
|. . . . . 6 3 8
. . . . . . .|1 4 5|2 7 . . . .
``````
``````The next value is (minimum <= value < maximum), place new values ​​(maximum and minimum) in ascending order column,
and let the value group arranged so far be Part.(Part: 27 completed)
|. . . . . . 3 8
. . . . . . .|1 4 5|2 7|6 . . .
``````
``````The next value is (value < minimum), place it below the descending column and update the minimum.
|. . . . . . . 8
. . . . . . 3|1 4 5|2 7|6 . . .
``````
``````The next value is (maximum <= value), place it above the ascending order column and update the maximum.(Part: 368 completed)
|. . . . . . . .
. . . . . .|3|1 4 5|2 7|6 8|. .
``````
``````External area result.
4 5|2 7|6 8|. .  Ascending column arrangement
. . . . . .|3|1  Descending column arrangement
4 5|2 7|6 8|3|1  Actual arrangement
``````
``````Merge generated Parts.
145  27  368
12457  368
12345678
Sort complete.
``````

# Improvement

We will make additional improvements to the basic algorithm.

• Insert sort is performed to secure the length of Part.
• Merge sequentially to avoid recursion.

# 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.16.27030.1 for x64

``````cl Main.cpp -std:c++14 -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe
``````

## clang++

clang version 8.0.0 (tags/RELEASE_800/final)
Target: x86_64-w64-windows-gnu

``````clang++ Main.cpp -std=c++14 -O3 -o TestClang++.exe
TestClang++.exe
``````

## g++

gcc version 8.3.0 (Rev2, Built by MSYS2 project)
Target: x86_64-w64-mingw32

``````g++ Main.cpp -std=c++14 -O3 -o TestG++.exe
TestG++.exe
``````

# Random number benchmark

Sorts float values ​​generated from the same seed.
The unit is seconds, the lower the number, the faster.

# Conditional benchmark

The following all sorted the array [100,000,000] of float value.
The unit is seconds, the lower the number, the faster.

# Finally

How was it?

Hayate-Shiki is a stable sort, but has strong characteristics to random numbers.
In the conditional benchmark, it was found that the influence of the optimization characteristic of the compiler, rather than the algorithm characteristic, becomes strong, so that it can hardly be a judgment material.

Does it come the day when merge sort wins quick sort?

The sort algorithm is still romantic.

Popular Algorithms Projects
Popular Sort Projects
Popular Computer Science Categories
Related Searches

Get A Weekly Email With Trending Projects For These Categories
No Spam. Unsubscribe easily at any time.
C Plus Plus
Database
Algorithms
Programming
Data Science
Benchmark
Sort
Computer Science