Character

которая содержит 4 серии: ch, ar, act, er. Разделив символы на 2 новые строки и переключаясь между строками после обработки каждой серии, будут созданы строки:

ch·act

ar·er

(точка не является частью строки, а лишь показывает разрыв между сериями).

Объединяя эти строки символ за символом, получим в результате:

После выполнения шага	Старые строки	Новая строка
	chact	arer
	chact	rer	a
	hact	rer	ac
	act	rer	ach
	ct	rer	acha
	t	rer	achac
	t	er	achacr
	t	r	achacre
	t		achacrer
			achacrert

Склеенная строка теперь содержит 3 серии: ach, acr, ert. Снова разделяем ее на две строки по сериям:

ach·ert

Acr

после объединения получим:

aacch·errt

Разделение строк дает:

Aacch

Errt

И третья операция слияния дает нам сортированную строку:

Aaccehrrt

Другой способ слияния – слежение за границами серий и перемещение всех символов в паре серий до рассмотрения следующее пары серий. Для выше упомянутого примера, разделив строку на:

ch·act

ar·er

после слияния мы получим:

aacch·errt

а после второго разделения/слияния мы получим отсортированную строку гораздо быстрее, чем при посимвольном слиянии.

Разница между слиянием по символам и слиянием по сериям огромная. Слияние по сериям гарантирует нам уменьшение количества серий наполовину, поскольку каждая пара серий будет превращена в одну серию. Слияние по символам не обладает таким свойством.

Сортируемый файл может уже содержать длинные серии, но может и не содержать. В общем случае нам могут быть гарантированы только серии единичной длины – отдельные символы. Если файл будет разделен на чередующиеся символы, то каждый кусочек будет содержать серии единичной длины. Затем они могут быть объединены для получения серий длиной в 2 символа. Разделяя файл на чередующиеся серии длины 2 и, объединяя их, мы получим серии длиной 4 символа и т.д. При этом, случайно возможные серии большей длины игнорируются, однако эта процедура стабильно приближает нас к конечному результату. Мы сможем избежать подсчета длины серий, если обозначим символом # искусственные границы серий. Пример данного процесса показан ниже для строки wrcaot:

Шаг	Разделенные строки	Склеенная строка
			w#r#c#a#o#t#
Разделение	w#c#o#	r#a#t#
Слияние			rw#ac#ot#
Разделение	rw#ot#	ac#
Слияние			acrw#ot
Разделение	acrw#	ot#
Слияние			acortw#