Merge Sort. Сортировка слиянием (C#)

В этой статье будет рассказано схему действия сортировки слиянием и пример реализации алгоритма на С#.
Итак, начнем.

Сортировка слиянием (marge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. (так говорит Википедия).

То есть, на входе мы получаем некий массив данных (для простоты и удобства, будем рассматривать целочисленный массив) на n элементов. Затем, делим этот массив на два подмассива размером n/2. И так до тех пор, пока массив не уменьшится до двух элементов, которые достаточно просто отсортировать. Как вы уже могли понять, процедура дробления осуществляется путем рекурсии.

После сравнения двух элементов наш процесс начинает возвращаться и собирать себя по отсортированным кусочкам массива. В процессе обратного слияния элементы подмассивов сравниваются между собой и в окончательный массив вставляется меньший элемент.

Так визуально выглядит этот принцип:

С определением разобрались, приступим к реализации.

Реализация.

Сортировка будет состоять из двух функций:
1. Sort - делит массив на подмасивы
2. MergeSort - сортирует и соединяет массивы

Так же у нас будет одна глобальная переменная number для подсчета количества инверсий.

Функция Sort() принимает и возвращает целочисленный массив.

1. static int[] Sort(int[] buff)

Сначала мы проверяем длину данного массива. И если она меньше или равна 1, то этот массив мы и возвращаем, так как он не нуждается в сортировке.
Далее инициализация и заполнение субмассивов.

1.   //массивы для хранения половинок входящего буфера
2.   int[] left = new int[buff.Length / 2];
3.   //для проверки ошибки некорректного разбиения массива,
4.   //в случае если длина непарное число
5.   int[] right = new int[buff.Length - left.Length];
6.                                
7.   //заполнение субмассивов данными из входящего массива
8.   for (int i = 0; i < left.Length; i++)
9.   {
10.         left[i] = buff[i];
11.   }
12.    for (int i = 0; i < right.Length; i++)
13.    {
14.         right[i] = buff[left.Length + i];
15.    }

Обращаю внимание, что длину субмассивов мы получаем не делением на 2 длинны основного массива. Почему? Очень просто, длинна массива может быть непарной. Для примера рассмотрим массив длиной 15. Если оба субмассива будут заполняться способом [buff.Length / 2], то мы получим два субмассива длинной 7 и 7. И у нас сразу возникает 2 ошибки - 1. потеря одного значения и 2. выход за границы при заполнении.
Поэтому делением на 2 мы определяем длину только первого субмассива, второй же мы определяем путем уменьшения длинны первоначального массива на длину уже созданного.

Дальше нам осталось проверить новые субмассивы. Если они длиннее единицы, то мы их снова делим. Если же нет - то мы их сортируем.

1. static int[] Sort(int[] buff)
2.  {
3.      //проверка длинны массива
4.      //если длина равна 1, то возвращаем массив, 
        //так как он не нуждается в сортировке
5.      if (buff.Length > 1)
6.      {
7.          //массивы для хранения половинок входящего буфера
8.          int[] left = new int[buff.Length / 2];
9.         //для проверки ошибки некорректного разбиения массива,
10.          //в случае если длина непарное число
11.          int[] right = new int[buff.Length - left.Length];
12.                            
13.          //заполнение субмассивов данными из входящего массива
14.          for (int i = 0; i < left.Length; i++)
15.          {
16.             left[i] = buff[i];
17.          }
18.          for (int i = 0; i < right.Length; i++)
19.          {
20.              right[i] = buff[left.Length + i];
21.          }
23.          //если длина субмассивов больше еденици,
24.          //то мы повторно (рекурсивно) вызываем функцию разбиения массива
25.          if (left.Length > 1)
26.              left = Sort(left);
27.          if (right.Length > 1)
28.              right = Sort(right);
29.          //сортировка слиянием половинок
30.          buff = MergeSort(left, right);
31.      }
32.     //возврат отсортированного массива
33.     return buff;
34.  }

Дальше рассмотрим как работает сама функция сортировки.

1. static int[] MergeSort(int[] left, int[] right)

Принимаем два субмассива и возвращаем уже соединенный отсортированный массив.

Так же в этой функции проходит подсчет инверсий. 

Инверсия - это количество ячеек, которое проходит переставляемое число, чтобы стать на свое новое место. 

То есть, когда мы 2 переставляем во вторую ячейку нового массива, между 1 и 3 мы за один шаг (одно сравнение) проходим три ячейки. В данном случае инверсия будет рана 3.

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

1. static int[] MergeSort(int[] left, int[] right)
2. {
3.     //буфер для отсортированного массива
4.     int[] buff = new int[left.Length + right.Length];
5.     //счетчики длины трех массивов
6.     int i = 0;  //соединенный массив
7.     int l = 0;  //левый массив
8.     int r = 0;  //правый массив
10.     //сортировка сравнением элементов
11.     for (; i < buff.Length; i++)
12.     {
13.         //если правая часть уже использована, дальнейшее движение происходит только в левой
14.         //проверка на выход правого массива за пределы
15.         if (r >= right.Length)
16.         {
17.             buff[i] = left[l];
18.             l++;
19.         }
21.         //проверка на выход за пределы левого массива
22.         //и сравнение текущих значений обоих массивов
23.         else if (l < left.Length && left[l] < right[r])
24.         {
25.             buff[i] = left[l];
26.             l++;
27.         }
29.         //если текущее значение правой части больше
30.         else
31.         {
32.             buff[i] = right[r];
33.             r++;
34.             //подсчет количества инверсий
35.             if (l < left.Length)
36.                 number += left.Length - l;
37.         }
38.     }
40.     //возврат отсортированного массива
41.     return buff;
42. }

Осталось самое простое. Main().

1. //подсчет инверсий
2. static double number;
4. static void Main(string[] args)
5. {
6.    number = 0;
7.    int[] arr = new int[6]{6,5,4,3,2,1};
8.    
9.    //вывод на экран несортированного массива
10.    foreach (int item in arr)
11.    {
12.         Console.Write(item.ToString() + " ");
13.    }
14.    Console.WriteLine("\n");
16.    arr = Sort(arr);
17.    //выводим количество инверсий
18.    Console.WriteLine("Инверсий:" + number.ToString() + "\n");
20.    //вывод на экран отсортированного массива
21.    foreach (int item in arr)
22.    {
23.         Console.Write(item.ToString() + " ");
24.    }
25.    Console.Read();
26. }

Полный код можно получить здесь.