Ви праві, повернув рекурсію. Складність зараз O(n + k), де n це для злиття, як і в класичному Merge Sort, k — для допоміжного масиву для збереження індексів хвиль, k <= n/2.

Код бенчмарку додав

Не зовсім зрозумів вас, другу половину прийдеться сортувати і потім мержити з першою в будь-якому разі.
І мерж буде юзати пам’ять додаткову, як без цього?

Абсолютно не розібравшись з предметною областю, цілий день мене тролиш так нічого не зрозумівши з моїх відповідей.
Я більше на твої пости відповідати не маю ніякого бажання.
Всього найкращого!

Послухайте, шановний. Ви спочатку почитайте документацію по методу, а потім пишіть. learn.microsoft.com/...​-array-sort(system-array
Ніколи не пиши не перевіривши, а то виглядаєш трохи непрофесійно.
В документації написано, що в залежності від кількості, використовуються HeapSort або QuickSort. Вони обидва НЕ СТАБІЛЬНІ і до цієї статті не мають жодного відношення.

Ні, не пробував, поки що це як концепт і ідея

Але то 14% як не як і це на цілих числах ;-)

Масив waves після першого проходу вже зберігає індекси всіх підмасивів, нічого не потрібно шукати.

Після знаходження всіх підмасивів методом поділу на 2, як і скрізь, розділяй і володарюй.

Я просто поділився реалізацією нового підходу і не претендую на використання мого підходу всім. Його теж можна розпаралелити, в чому проблема.
Нижче в коментах навів бенчмарки чисто рандомних масивів і тут продублюю:

int[] CreateRandomArray(int size)
{
	var array = new int[size];
	var rand = new Random();
	for (int i = 0; i < size; i++)
		array[i] = rand.Next(0, 9999);
	return array;
}

N = 1M, Wave Sort: 312.0242ms, Merge Sort: 364.8288ms
N = 2M, Wave Sort: 638.6731ms, Merge Sort: 740.0590ms
N = 5M, Wave Sort: 1699.7112ms, Merge Sort: 2004.5810ms
N = 10M, Wave Sort: 3462.7547ms, Merge Sort: 4011.3034ms

Я ні з ким не збирався конкурувати і нічого не накручував. Алгоритм лежить на GitHub, можна брати і перевіряти без «моїх накруток».
Просто хотів поділитись, а ви якийсь холівар з того розводите і ще й звинувачуєте мене бездоказно і безпідставно.
Візьміть і порівняйте кількість операцій і все стане ясно.
Даний приклад і бенчмарки на цілих числах відбуваються, де ціна операції порівняння низька.
Уявіть, якщо порівняння буде по тексту або ще й по декільком ключам. От тоді кількість операцій стане в нагоді і перетвориться на більш суттєвий часовий проміжок.
Ну і щодо Timsort (ще раз кажу, що ні в якому разі не хочу применшити чи чимось образити розробників існуючих алгоритмів):
1. Візьмемо масив розміром 32 (як і дефолтовий run у Timsort) повністю сортований по спаданню (найгірший випадок для Timsort)
2. Тімсорт виконає 31*32/2 = 496 замін і стільки ж порівнянь
3. Wave Sort зробить 31 порівняння і 16 замін.
-----------------------
1. Візьмемо wave array (він же синусоїда) розміром 32 (найгірший випадок для Wave Sort)
2. Wave Sort зробить 123 порівняння і 98 замін
3. Timsort зробить 208 порівняннь і 200 замін
-----------------------
Як і обіцяв, цифри по мільйонам (якщо захочете вірити):
N = 1M, Wave Sort: 312.0242ms, Merge Sort: 364.8288ms
N = 2M, Wave Sort: 638.6731ms, Merge Sort: 740.0590ms
N = 5M, Wave Sort: 1699.7112ms, Merge Sort: 2004.5810ms
N = 10M, Wave Sort: 3462.7547ms, Merge Sort: 4011.3034ms

Вже писав нижче, але повторю:
Алгоритми сортування зазвичай подаються на прикладі масиву цілих чисел, де ціна порівняння невисока, і мої бенчмарки теж їх використовують. А тепер уявіть, що ви сортуєте об’єкти по ключам складніших типів або цих ключів може бути декілька і ціна оперції порівняння буде значно вищою. І там кількість порівнянь вже себе на часовому проміжку краще покаже.

Але ж ви користуєтесь базами данних і швидше за все там сортуються результати для ваших продуктів. Ось там сортування і використовується. Знову ж, є домени, які можуть це використовувати досить серйозно, наприклад, фізичні, медичні чи біологічні дослідження.

Дякую, можна спробувати, але тоді ще треба цей признак десь зберігати. Та й не думаю, що на цьому можна виграти в сенсі кількості операцій. Перевертання — простий і не затратний метод.

Вибачте, вже вище про Тім сорт написав, так, він — гібрид.
Так, мій стабільний. Доберусь до компа і пришлю тести для мільйону)

Я згоден, що Тім Петерс покращив мерж сорт, беручи підмасиви заданої довжини, сортуючи їх за допомогою insertion sort, а потім зливаючи їх алгоритмом мерж сорта.
Але знову, кількість операцій не оптимальна.
В мене інше рішення і навіть метод злиття інший, ніж класичний.
Алгоритми сортування зазвичай подаються на прикладі масиву цілих чисел. А тепер уявіть, що ви сортуєте об’єкти по ключам складніших типів або цих ключів може бути декілька і ціна оперції порівняння буде значно вищою. Ось тут всі і згадають про оптимізацію кількості порівнянь.

Дякую за фідбек. Відповідаю:
1. З bubble sort немає сенсу порівнювати, бо на значних об’ємах він виграє тільки на вже відсортованому масиві.
2. Код бенчмарку не наводив, думаю, що тут кожен його напише за 10 хв, взявши коди відповідних алгоритмів. За залізо згоден, але тести проводились на тій самій машині, і тут вже відіграє роль в кількості операцій порівняння і заміни.
3. Чому ж мерж сорт не мейнстрім? Який по вашому алгоритм використовується в базах даних для сортування великих об’ємів? Timsort — то похідний від мерж сорту, а quick sort — нестабільний, тому тут йому точно не місце.
4. За назви даних вибачте, просто показав параболу, як приклад з великими діапазонами сортованих підмасивів всередині.
5. Ну я б не сказав, що 200к — то малий об’єм даних і bubble sort там би точно загнувся.
6. Згоден, що алгоритми використовують з оптимізаціями і паралельними обчисленнями. Те ж саме можна зробити і з даним алгоритмом. Я всього лише показав підхід з аналізом даних і формуванням підмасивів для злиття, які вже природньо відсортовані в масиві. Це, як на мене, дає мінімальну кількість операцій, що є важливим для таких алгоритмів.

O(n + k), де n це для злиття, як і в класичному Merge Sort, k — для допоміжного масиву для збереження індексів хвиль.
В даному випадку k = n/3 + 2, тож загальний виходить O(4n/3 +2).

Так це ж базовий алгоритм, що не мав би спиратись на інші функції. Тоді можно було і Array.Sort заюзати.