Сортировка слиянием (merge sort) на C#

Привет! Сегодня рассмотрим крутой метод сортировки слиянием.

Автор данного метода известный математик Джон фон Нейман, внёсший не малый вклад в науку по информатике.

Данный бриллиант был разработан в 1945 году.

Алгоритм сортировки слиянием использует рекурсию и ярко характеризует принцип "разделяй и властвуй".

Время работы пропорционально n*log(n), где n - длина массива. Это лучший показатель, по сравнению с уже разобранными алгоритмами сортировки на этом сайте.

Мы будем сегодня программировать на языке C# (Си шарп).

Для начала зафиксируем тот факт, что если мы передадим в функцию массив, то изменения массива в функции приведут к изменениям в самом массиве. Это происходит из-за того, что программа продолжает ссылаться на тот же массив. Рассмотрим пример.

static void Main(string[] args)
{
    int i;
            
    int[] a = { 7, 0, -4, 3, 1, -2, 5 };

    for(i=0; i < a.Length; i++)
    {
        Console.WriteLine(a[i]);
    }

    Test(a);

    Console.WriteLine();

    for (i = 0; i < a.Length; i++)
    {
        Console.WriteLine(a[i]);
    }
}

static void Test(int[] b)
{
    b[0] = b[0] * 7;
}

Здесь мы изменили первый элемент массива в функции Test, и это отразилось на самом массиве.

Вернёмся к сортировке методом слияния. Пусть наш массив разделён примерно на две равные части, причём обе части уже отсортированные!

Тогда можно легко полностью отсортировать данный массив. Напишем функцию слияния:

static void Merge(int[] a, int l, int m, int r)
{
    int i, j, k;

    int n1 = m - l + 1;
    int n2 = r - m;

    int[] left = new int[n1+1];
    int[] right = new int[n2+1];

    for(i=0; i < n1; i++)
    {
        left[i] = a[l+i];
    }

    for (j = 1; j <= n2; j++)
    {
        right[j-1] = a[m+j];
    }

    left[n1] = int.MaxValue;
    right[n2] = int.MaxValue;

    i = 0;
    j = 0;

    for(k=l; k <= r; k++)
    {
        if(left[i] < right[j])
        {
            a[k]=left[i];
            i = i + 1;
        }
        else
        {
            a[k]=right[j];
            j = j + 1;
        }
    }
}

Параметры функции: a - массив, который разделён на две отсортированные части, l - индекс начала левой отсортированной части, m - это индекс последнего элемента левой части (примерная середина массива a), r - это индекс последнего элемента правой отсортированной части (индекс последнего элемента массива a).

left и right - это массивы, куда переносим отсортированные половинки массива a. Длины для этих массивов вычисляются в переменных n1 и n2. Если количество элементов в массиве a нечётно, то n1 будет на 1 больше, чем n2, иначе, эти переменные равны.

Чтобы теперь слить, объединить два отсортированных массива, будем брать два самых маленьких элемента из массивов left и right и сравнивать между собой. Меньший элемент пойдёт в 0-ой индекс массива a, тем самым мы начинаем пересобирать массив a, раскладывая элементы по порядку.

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

Но создаём массивы left и right c длинами n1+1 и n2+1 соответственно. Последний элемент мы положим сами, это будет очень большое число int.MaxValue. Это максимальное значение для типа int, оно равно 2147483647. Данный элемент считается индикатором того, что в массиве left (или right) закончились элементы. Предполагается, что числа в массивах меньше, чем наибольшее значение типа int. Если мы дошли до элемента int.MaxValue в каком-либо массиве, то элементы из другого массива не смогут "победить" это значение, и будут записываться в массив a последовательно.

При необходимости сигнальные элементы int.MaxValue можно заменить на механизм проверки того, что в каком-то массиве закончились элементы.

Итак, результатом работы функции Merge будет отсортированный массив a. Теперь применим рекурсию для функции Merge.

static void MergeSort(int[] a, int l, int r)
{
    int q;

    if (l < r)
    {
        q = (l + r) / 2;
        MergeSort(a, l, q);
        MergeSort(a, q + 1, r);
        Merge(a, l, q, r);
    }
}

Параметры функции: a - массив, который нужно отсортировать, l - индекс левой границы сортируемой области, r - индекс правой границы сортируемой области.

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

В начале к нам поступает неотсортированный массив. Его мы условно делим на две части, и применяем к обеим частям опять эту же функцию MergeSort. Хотим каждую часть отсортировать. Затем опять происходит тоже самое, пока программа не расщепит сортируемую область до одного элемента. Как мы уже говорили, один элемент уже считается отсортированным, и это главный момент сортировки слиянием!

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

Приведём пример использования сортировки слиянием на конкретном массиве.

static void Main(string[] args)
{
    int[] a = { 7, 0, -4, 3, 1, -2, 5 };
    int l = 0;
    int r = a.Length-1;

    MergeSort(a, l, r);

    for(int i=0; i < a.Length; i++)
    {
        Console.WriteLine(a[i]);
    }            
}