Естественная сортировка слиянием связанного списка

Я искал естественную реализацию сортировки слиянием(связанные списки)какое-то время, но не повезло.

Сортировка слиянием связанного списка

Здесь у нас есть и рекурсивная, и итеративная реализация, но я не знаю, как превратить это в естественную сортировку слиянием.

Как мне проверить, чтобы прогоны в лучшем случае имели O(n)сложность? Это не обязательно должен быть C/C++, это может быть любой язык или даже псевдокод.

Спасибо.