Естественное слияние

Предыдущий метод не учитывает того факта, что в исходной последовательности уже могут быть упорядоченные подпоследовательности. Они называются сериями. Это последовательности вида:

A[L],A[L+1],…A[k],

такая, что:

A[L] A[L+1] …A[k],

A[L-1]>A[L],

A[k+1]<A[k].

Метод работает так: сначала первая серия посылается на ленту В, вторая- на ленту С, третья- на ленту В, четвертая на С и т.д. Первая серия с ленты В сливается с первой серией ленты С. В результате на ленте А куда сливаются эти серии появится 1-ая увеличенная серия.

Затем вторая серия ленты В сливается со второй серией ленты С и т.д. После выполнения всех вариантных слияний количество серий на ленте А окажется в двое меньше, чем в исходной последовательности. Затем снова разделение серий, снова слияние и т.д.