Wave Merge Sort

A new stable sorting algorithm that use merging prepared waves (sorted sub-arrays).

This is a FREE algorithm, you can use it in your products without any licenses.

Algorithm

1. Walking through the array, we will encounter either increasing values (or identical values) or decreasing values. I called these ranges waves because a wave also has an up side and a down side.
2. We reverse falling waves, getting growth waves. Thus, after passing the entire array, we will have only growth waves or equal waves, if their sorting keys are the same..
3. Keeping the indices of the ends of the waves, we will have a set of sorted subarrays ready for the final merge.
4. Well, in the end, the sorted subarrays merge and the given array is sorted.

Example

Given the following array:

The figure below shows the steps of the algorithm described above:

Is Wave Merge Sort stable?

Yes, this algorithm is stable.

Time complexity

Best Case: O(n)

Average Case: O(n log n)

Worst Case: O(n log n)

Auxiliary space

O(n + k) – The algorithm uses auxiliary arrays to merge waves (n) and save wave indices (k).

Advantages

• Quick sorting of already sorted (whether in ascending or descending order) arrays or if the array has sufficiently significant such ranges

• The minimum number of comparison and swap operations compared to the classic Merge Sort

Disadvantages

• Allocation of auxiliary arrays for merging and saving wave indices

Benchmarks

It's time to compare the results of the Merge Sort and Wave Merge Sort algorithms.

Below is the average running time for different arrays by size and distribution of elements. The average time is taken from 20 runs of each species.

Sponsorship

If you like it and want to support me, please use links in the "Sponsor this project" section on this page.