==============================================================
> 10. Описание MergeSort (сортировка слиянием).
==============================================================
  
Слиянием называется процесс объединения нескольких 
упорядоченных серий(т.е упорядоченных списков) в  одну.

 Пример для 3-х серий, слияемых на 4-ю:

    3 7 9      3 7 9        3 7 9          7 9             7 9
  { 2 4 6  1 { 2 4 6  1 2 { 4 6    1 2 3 { 4 6   1 2 3 4 { 6
    1 5 8      5 8          5 8            5 8             5 8

               7 9                7 9                 9
   1 2 3 4 5 { 6    1 2 3 4 5 6 { 8     1 2 3 5 6 7 { 8   1 2 3 4 5 6 7 8 9 {
               8
				   
  Hа каждом шаге мы беpем наименьший из начальных элементов входных
серий и перемещаем в конец выходной серии. 
  Каждая операция слияния серий, очевидно, требует n пересылок
 элементов, где n - общее число элементов серий.
 		
 Для применения MergeSort в качестве внутренней сортировки 
 можно записать рекурсивный алгоритм всего в несколько строчек, 
 пользуясь подходом разделяй-и-властвуй:

list-type mergesort (list-type L; int n)  { 
if (n = 1) return (L) else { 
    разделить L на две половины L1 и L2; 
    return (merge (mergesort (L1,n/2), mergesort (L2,n/2)) );
    } 
}
merge() - функция слияния. 

  Хорошо(не так, как выше) запрограммированная внутренняя сортировка 
слиянием работает немного быстрее пирамидальной, но медленнее быстрой.
Hо при этом она требует Omega(n) дополнительной памяти,
поэтому применяют MergeSort только для внешней сортировки(файлов и т.п),
где используемое пространство не настолько критично,
а доступ к произвольному элементу осуществляется сравнительно медлененно.
		   
  Алгоритм простого слияния.
  
 1. Последовательность а разбивается на две половины b и c
 2. Последовательности b и c сливаются при помощи объединения
  элементов в упорядоченные пары.
 3. Полученной последовательности присваивается имя а, и
 повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются
 в упорядученные четверки.
 4. Предыдущие шаги повторяются: четверки сливаются в восьмерки, и весь 
 процесс продолжается до тех пор, пока не будет упорядочена вся 
 последовательность, ведь длины сливаемых последовательностей каждый
 раз удваиваются.
 
   Пример: последовательность 44 55 12 42 94 18 06 67
   
 Hа первом шаге разбиение дает последовательности
          44 55 12 42
          94 18 06 67
 Слияние отдельных компонент (которые являются упорядоченными
 последовательностями длины 1) в упорядоченные пары дает:
         44 94 ' 18 55 ' 06 12 ' 42 67
 Hовое разбиение и слияние упорядоченных пар дает:
         06 12 44 94 ' 18 42 55 67
 Третье разбиение и слияние приводят к нужному результату:
         06 12 18 42 44 55 67 94.
		 
 Операция, которая однократно обрабатывает все множество данных, 
 называется 'фазой', а наименьший процесс, который, повторяясь, 
 образует процесс сортировки, называется 'проходом' или 'этапом'.
 В приведенном выше примере сортировка производится за три прохода,
 каждый проход состоит из фазы разбиения и фазы слияния.
 Для выполнения сортировки требуются три списка(ленты, файла),
 поэтому процесс называется трехпутевым(трехленточным) слиянием.  
  
 Hа этом же принципе основаны и другие, более сложные и эффективные
сортировки слиянием, как-то: естественное слияние, многопутевое
сбалансированное слияние, каскадная и многофазная сортировки.

 Для получения более подробной информации рекомундую почитать
  H.Вирт "Алгоритмы + Структуры данных = Программы".
 
 - однофазное/сбалансированное слияние (4-путевое)
 - естественное слияние
 - сбалансированное многопутевое слияние ( N/2-путевое )
 - многофазная сортировка слиянием ( N-1-путевое слияние )

  Д.Кнут "Искуссво программирования на ЭВМ" 
 
 По памяти - приблизительно то же, хуже описана многофазная, 
 но есть

 - каскадная сортировка слиянием
 - осциллирующая сортировка слиянием
  


 
 Многофазная сортировка слиянием будет описана в вопросе
о сортировке файлов. Там же будет дан ее исходник.

 На практике она имеет приблизительно ту же эффективность, что
и каскадная сортировка слиянием - наилучшую для данного класса методов.