Сортування злиттям

Сортування злиттям (Merge sort) – алгоритм сортування масиву, який реалізовано по принципу “розділяй і володарюй”. Задача сортування масиву розбивається на декілька підзадач з сортуванням масивів меншого розміру, після виконання яких, результат комбінується, що і приводить до вирішення початкового завдання.

Опис алгоритму сортування злиттям

Алгоритм сортування злиттям виглядає наступним чином:

  • Вхідний масив розбивається на дві частини однакового розміру;
  • Кожен з підмасивів сортується окремо, по цьому ж принципу, тобто відбувається повторне розбиття до тих пір, поки довжина підмавису не досягне одиниці. В такому випадку кожен одиночний масив вважається відсортованим;
  • Після цього відбувається злиття всіх підмасивів в один, в результаті чого отримуємо відсортовані дані.

Реалізація сортування злиттям

using System;

class Program
{
    //метод для злиття масивів
    static void Merge(int[] array, int lowIndex, int middleIndex, int highIndex)
    {
        var left = lowIndex;
        var right = middleIndex + 1;
        var tempArray = new int[highIndex - lowIndex + 1];
        var index = 0;

        while ((left <= middleIndex) && (right <= highIndex))
        {
            if (array[left] < array[right])
            {
                tempArray[index] = array[left];
                left++;
            }
            else
            {
                tempArray[index] = array[right];
                right++;
            }

            index++;
        }

        for (var i = left; i <= middleIndex; i++)
        {
            tempArray[index] = array[i];
            index++;
        }

        for (var i = right; i <= highIndex; i++)
        {
            tempArray[index] = array[i];
            index++;
        }

        for (var i = 0; i < tempArray.Length; i++)
        {
            array[lowIndex + i] = tempArray[i];
        }
    }

    //сортування злиттям
    static int[] MergeSort(int[] array, int lowIndex, int highIndex)
    {
        if (lowIndex < highIndex)
        {
            var middleIndex = (lowIndex + highIndex) / 2;
            MergeSort(array, lowIndex, middleIndex);
            MergeSort(array, middleIndex + 1, highIndex);
            Merge(array, lowIndex, middleIndex, highIndex);
        }

        return array;
    }

    static int[] MergeSort(int[] array)
    {
        return MergeSort(array, 0, array.Length - 1);
    }


    static void Main(string[] args)
    {
        Console.WriteLine("Сортування злиттям");
        Console.Write("Введіть елементи масиву: ");
        var s = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
        var array = new int[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            array[i] = Convert.ToInt32(s[i]);
        }

        Console.WriteLine("Впорядкований масив: {0}", string.Join(", ", MergeSort(array)));

        Console.ReadLine();
    }
}

Результат роботи програми:

Дивіться також: