Merge sort

A merge vagy magyar nevén összefűzéses rendezés egy olyan rendezési algoritmus, ami az „oszd meg és uralkodj” elvet alkalmazza. Az algoritmus előnye, hogy mindig O (n log n) futási idővel rendelkezik, még a legrosszabb esetben is.

Az algoritmus a bemeneti tömböt kettéosztja két kisebb részre, egészen addig, amíg minden rész csak egyetlen egy elemet tartalmaz. Az egy elemű tömbök pedig már eleve rendezettnek tekinthetőek. Ezt követően a rendezett részeket páronként összefésüli úgy, hogy az eredmény is rendezett legyen. Ez addig ismétlődik, amíg az egész tömb újra össze nem áll.

A merge sort „hagyományos” implementációja rekurzív, de ez nagyobb méretű tömbök esetén nem alkalmazható, hiszen könnyen stack overflow-t kaphatunk. Az algoritmus hátránya, hogy az összevonásokhoz további tömböket allokál a szükséges részhalmazok ideiglenes tárolásához, ami nagy tömbök esetén jelentős extra memóriaterhelést okoz. C# esetén az extra memóriaallokációk csökkenthetőek, ha a rész tömbök helyett Span<T> típusokat allokálunk.

Egy lehetséges iteratív implementáció:

using System;

namespace PeldaAlgoritmusMergeSort
{
    class Program
    {
        static void TombKiir(int[] tomb)
        {
            foreach (var elem in tomb)
            {
                Console.Write("{0}, ", elem);
            }
            Console.WriteLine();
        }

        public static int[] MergeSort(int[] bemenet)
        {
            int[] tomb = new int[bemenet.Length];
            Array.Copy(bemenet, tomb, bemenet.Length);

            if (tomb.Length < 2)
                return tomb;

            // Lépésméret: kezdetben 1, majd 2, 4, 8, ...
            for (int meret = 1; meret < tomb.Length; meret *= 2)
            {
                // A bal kezdő index kiválasztása az aktuális lépésmérethez
                for (int bal = 0; bal < tomb.Length - 1; bal += 2 * meret)
                {
                    int kozepe = Math.Min(bal + meret - 1, tomb.Length - 1);
                    int jobb = Math.Min(bal + (2 * meret) - 1, tomb.Length - 1);

                    //Összefűzés
                    Merge(tomb, bal, kozepe, jobb);
                }
            }

            return tomb;
        }

        private static void Merge(int[] tomb, int bal, int kozepe, int jobb)
        {
            int balMeret = kozepe - bal + 1;
            int jobbMeret = jobb - kozepe;

            int[] balTomb = new int[balMeret];
            int[] jobbTomb = new int[jobbMeret];

            Array.Copy(tomb, bal, balTomb, 0, balMeret);
            Array.Copy(tomb, kozepe + 1, jobbTomb, 0, jobbMeret);

            int balIndex = 0;
            int jobbIndex = 0;
            int k = bal;

            while (balIndex < balMeret
                && jobbIndex < jobbTomb.Length)
            {
                if (balTomb[balIndex] <= jobbTomb[jobbIndex])
                {
                    tomb[k++] = balTomb[balIndex++];
                }
                else
                {
                    tomb[k++] = jobbTomb[jobbIndex++];
                }
            }

            if (balIndex < balMeret)
            {
                Array.Copy(balTomb, balIndex, tomb, k, balMeret - balIndex);
                k += balMeret - balIndex;
            }

            if (jobbIndex < jobbMeret)
            {
                Array.Copy(jobbTomb, jobbIndex, tomb, k, jobbMeret - jobbIndex);
            }
        }


        static void Main(string[] args)
        {
            var tomb = new int[] { 9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6 };

            Console.WriteLine("Rendezés előtt:");
            TombKiir(tomb);

            Console.WriteLine("Merge rendezés:");
            var merge = MergeSort(tomb);
            TombKiir(merge);

            Console.ReadKey();
        }
    }
}

A program kimenete:

Rendezés elott:
9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6, 
Merge rendezés:
0, 0, 1, 1, 2, 2, 2, 2, 3, 4, 5, 6, 6, 8, 8, 9, 

Az algoritmus egy vizuális reprezentációja a YouTube-on: