Sorting Algoritmaları 1: Insertion Sort, Merge Sort ve Stability

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore'un sipariş listesi veritabanından tarih sırasıyla geliyor. Müşteri hizmetleri ekranı bu listeyi müşteri adına göre gruplamak istiyor; bir geliştirici Array.Sort(orders, byCustomer) yazıyor. Ekip, her müşterinin siparişlerinin ekranda yine tarih sırasında görüneceğini varsayıyor; sonuçta liste zaten tarihe göre sıralıydı.

Bu varsayım doğru mu? İkinci soru: 10.000 elemanlı, neredeyse sıralı bir fiyat listesini (yalnızca yüzde 1'i yer değiştirmiş) O(n²) olan insertion sort ile mi, O(n log n) olan Array.Sort ile mi sıralamak daha hızlı?

Selection ve Bubble Sort: Yalnız Karşılaştırma İçin

Ders kitaplarının ilk iki sorting algoritması production'da neredeyse hiç kullanılmaz, ama neyin neden daha iyi olduğunu görmek için kısa bir bakışa değerler:

namespace Algorithms.Sorting;

public static class SimpleSorts
{
    // girdi ne olursa olsun n^2/2 karşılaştırma; en fazla n-1 swap. Stable değil.
    public static void SelectionSort<T>(Span<T> items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        for (int i = 0; i < items.Length - 1; i++)
        {
            int min = i;
            for (int j = i + 1; j < items.Length; j++)
                if (comparer.Compare(items[j], items[min]) < 0) min = j;
            (items[i], items[min]) = (items[min], items[i]);
        }
    }

    // hiç swap yapmayan bir turda erken durur. Stable.
    public static void BubbleSort<T>(Span<T> items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        for (int end = items.Length - 1; end > 0; end--)
        {
            bool swapped = false;
            for (int j = 0; j < end; j++)
            {
                if (comparer.Compare(items[j], items[j + 1]) <= 0) continue;
                (items[j], items[j + 1]) = (items[j + 1], items[j]);
                swapped = true;
            }
            if (!swapped) return;
        }
    }
}

Selection sort her turda kalan kısmın en küçüğünü bulup başa koyuyor. Girdi zaten sıralı olsa bile n²/2 karşılaştırma yapıyor; tek avantajı en fazla n − 1 swap, yani yazmanın çok pahalı olduğu ortamlarda bir anlamı var. Uzaktaki element'leri takas ettiği için stable değil. Bubble sort komşuları karşılaştırıp yer değiştiriyor; erken çıkış sayesinde sıralı girdide tek turda bitiyor ama genel durumda bütün O(n²) algoritmaların en yavaşı. Seri boyunca ikisini de yalnızca testlerde referans olarak kullanacağız.

Insertion Sort: Küçük ve Neredeyse Sıralı Veride Hâlâ Değerli

Insertion sort, elindeki iskambil kartlarını sıralamak gibi çalışıyor: soldaki kısım her zaman sıralı; sıradaki element'i alıp kendisinden büyük olanları birer sağa kaydırarak doğru yere bırakıyorsun.

// büyük element'leri sağa kaydırıp mevcut element'i boşluğa bırakır. Stable, in-place.
// neredeyse sıralı input: her element yalnızca biraz hareket eder, toplam iş n'e yakın.
public static void InsertionSort<T>(Span<T> items, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    for (int i = 1; i < items.Length; i++)
    {
        T current = items[i];
        int j = i - 1;
        // katı > eşit element'leri orijinal sıralarında bırakır: stable olmasını sağlayan bu
        while (j >= 0 && comparer.Compare(items[j], current) > 0)
        {
            items[j + 1] = items[j];
            j--;
        }
        items[j + 1] = current;
    }
}

En kötü durumda (ters sıralı girdi) her element baştan sona kayıyor: O(n²). Ama maliyetin doğru ifadesi O(n + inversion sayısı); inversion, yanlış sırada duran bir element çifti. Neredeyse sıralı bir listede inversion sayısı küçük ve insertion sort neredeyse doğrusal çalışıyor. Küçük n'de ise sabitleri o kadar düşük ki karmaşık algoritmaları geçiyor: ek bellek yok, recursion yok, ardışık bellek erişimi var. .NET'in Array.Sort'u da bu yüzden 16 veya daha az elemanlı partition'larda insertion sort'a geçiyor; Microsoft Learn'deki Remarks bölümü bunu açıkça yazıyor.

Merge Sort: Böl, Sırala, Birleştir

Merge sort divide and conquer'ın ders kitabı örneği: array'i ikiye böl, iki yarıyı recursive sırala, iki sıralı yarıyı tek geçişte birleştir. Serinin üçüncü yazısında iki sıralı linked list'i birleştiren MergeSorted'ı yazmıştık; array versiyonu aynı fikir.

namespace Algorithms.Sorting;

public static class MergeSort
{
    public static void TopDown<T>(T[] items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        T[] buffer = new T[items.Length]; // O(n) ek bellek, bir kez ayrılıyor
        Sort(items, buffer, 0, items.Length, comparer);
    }

    private static void Sort<T>(T[] items, T[] buffer, int lo, int hi, IComparer<T> comparer)
    {
        if (hi - lo < 2) return;                 // 0 ya da 1 element: zaten sıralı
        int mid = lo + (hi - lo) / 2;
        Sort(items, buffer, lo, mid, comparer);  // [lo, mid)
        Sort(items, buffer, mid, hi, comparer);  // [mid, hi)
        if (comparer.Compare(items[mid - 1], items[mid]) <= 0) return; // yarılar zaten sırada
        Merge(items, buffer, lo, mid, hi, comparer);
    }

    public static void BottomUp<T>(T[] items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        T[] buffer = new T[items.Length];
        // önce 1'lik, sonra 2'lik, sonra 4'lük run'ları birleştir: hiç recursion yok
        for (int width = 1; width < items.Length; width *= 2)
        {
            for (int lo = 0; lo < items.Length - width; lo += 2 * width)
            {
                int mid = lo + width;
                int hi = Math.Min(lo + 2 * width, items.Length);
                Merge(items, buffer, lo, mid, hi, comparer);
            }
        }
    }

    private static void Merge<T>(T[] items, T[] buffer, int lo, int mid, int hi, IComparer<T> comparer)
    {
        Array.Copy(items, lo, buffer, lo, hi - lo);
        int left = lo, right = mid;
        for (int k = lo; k < hi; k++)
        {
            if (left == mid) items[k] = buffer[right++];
            else if (right == hi) items[k] = buffer[left++];
            // <= : eşitlikte soldaki (önceki) element kazanır, eşit element'ler sıralarını korur: stable
            else if (comparer.Compare(buffer[left], buffer[right]) <= 0) items[k] = buffer[left++];
            else items[k] = buffer[right++];
        }
    }
}

Tree'nin her seviyesinde toplam n element birleştiriliyor ve log₂ n seviye var: n log n. Bu, girdi ne olursa olsun geçerli. Merge sort'un en iyi, ortalama ve en kötü durumu aynı, quick sort'un aksine kötü bir girdisi yok. Recurrence'tan bu sonucu çıkarmak Big-O ve Complexity serisinin "Koddan Time Complexity Çıkarmak" yazısında. Sort'taki erken çıkış (sol yarının son elemanı sağ yarının ilkinden büyük değilse birleştirmeye gerek yok) küçük ama etkili bir optimizasyon: sıralı girdide merge sort'u O(n)'e indiriyor.

Bedeli O(n) ek bellek: buffer. Top-down versiyonun recursion derinliği log₂ n, yani 1 milyon element için 20 frame; serinin beşinci yazısındaki stack overflow kaygısı burada yok. Bottom-up versiyon recursion'ı tamamen kaldırıyor: genişliği 1, 2, 4, ... olan komşu run'ları döngüyle birleştiriyor. İkisi aynı sonucu veriyor ve testler bunu doğruluyor:

[Theory]
[MemberData(nameof(Algorithms))]
public void Sort_RandomAndEdgeInputs_MatchesArraySort(string name)
{
    Random random = new(11);
    int[][] inputs =
    [
        [], [1], [2, 1], [5, 5, 5],
        [.. Enumerable.Range(0, 100)],
        [.. Enumerable.Range(0, 100).Reverse()],
        [.. Enumerable.Range(0, 1_000).Select(_ => random.Next(50))],
        [.. Enumerable.Range(0, 777).Select(_ => random.Next())],
    ];
    foreach (int[] input in inputs)
    {
        int[] expected = [.. input];
        Array.Sort(expected);
        int[] actual = [.. input];

        Run(name, actual);

        Assert.Equal(expected, actual);
    }
}

Girdiler bilinçli seçildi: boş array, tek element, iki element, hepsi eşit, sıralı, ters sıralı, çok tekrarlı (0–49 arası 1.000 sayı) ve ikinin kuvveti olmayan bir uzunluk (777, bottom-up'ın son eksik run'ını test ediyor). Sorting hatalarının çoğu bu kenar durumlarında saklanıyor.

Büyük veride merge sort'un bir akrabası da çok kullanılıyor: external merge sort. Belleğe sığmayan 50 GB'lık bir sipariş log'unu sıralamak için dosyayı belleğe sığan parçalara bölüp her parçayı ayrı sıralıyor ve diske "run" olarak yazıyorsun; sonra bütün run'ları aynı anda okuyup her adımda en küçük başı seçerek tek bir sıralı dosyada birleştiriyorsun. Veritabanlarının bellekten büyük ORDER BY'ları bu şekilde çalışıyor. K tane run'ın en küçük başını hızlıca seçmenin yolu bir min-heap; onu serinin heap yazısında göreceğiz.

Ölçüm: Küçük, Rastgele ve Neredeyse Sıralı

Benchmark üç algoritmayı üç boyutta ve iki tür girdide ölçüyor. Neredeyse sıralı girdi, sıralı bir listede pozisyonların yüzde 1'inin komşusuyla yer değiştirmesiyle üretiliyor; birkaç fiyatı değişmiş sıralı bir liste gibi. Her ölçüm önce kaynak array'i çalışma array'ine kopyalıyor; kopyalama maliyeti üç algoritmada da aynı.

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method       | N     | Input         | Mean              | Ratio | Allocated |
|------------- |------ |-------------- |------------------:|------:|----------:|
| ArraySort    | 16    | random        |         35.077 ns |  1.00 |         - |
| Insertion    | 16    | random        |         50.678 ns |  1.45 |         - |
| MergeTopDown | 16    | random        |         91.259 ns |  2.60 |      88 B |
|              |       |               |                   |       |           |
| ArraySort    | 1000  | random        |      6,732.024 ns |  1.01 |         - |
| Insertion    | 1000  | random        |    145,942.100 ns | 21.79 |         - |
| MergeTopDown | 1000  | random        |     14,383.555 ns |  2.15 |    4024 B |
|              |       |               |                   |       |           |
| ArraySort    | 10000 | random        |    190,747.053 ns |  1.01 |         - |
| Insertion    | 10000 | random        | 16,098,611.987 ns | 85.24 |         - |
| MergeTopDown | 10000 | random        |    394,038.485 ns |  2.09 |   40024 B |
|              |       |               |                   |       |           |
| ArraySort    | 10000 | nearly-sorted |     34,182.605 ns |  1.00 |         - |
| Insertion    | 10000 | nearly-sorted |      5,755.829 ns |  0.17 |         - |
| MergeTopDown | 10000 | nearly-sorted |     21,309.086 ns |  0.62 |   40024 B |

Rastgele girdide beklenen tablo: insertion sort n büyüdükçe çöküyor; 10.000 elemanda Array.Sort'tan 85 kat yavaş. N 10 kat büyüdü, insertion sort'un süresi 110 kat büyüdü, quadratic büyüme. Merge sort Array.Sort'un iki katı civarında kalıyor ve n kadar ek bellek ayırıyor (int başına 4 byte, 10.000 için 40.024 byte).

Neredeyse sıralı girdide tablo tersine dönüyor ve ikinci sorunun cevabı burada: O(n²) insertion sort, Array.Sort'tan 6 kat hızlı. 10.000 elemanda yalnızca 100 komşu çift yer değiştirmiş; insertion sort her element için en fazla bir adım geri gidiyor ve iş neredeyse n karşılaştırma. Merge sort da erken çıkış sayesinde Array.Sort'u geçiyor. Introsort ise girdinin zaten sıralı olduğunu fark edecek bir kontrole sahip değil, partition yapmaya devam ediyor. 16 elemanda Array.Sort zaten insertion sort çalıştırıyor; bizim versiyonumuz ondan biraz yavaş, çünkü BCL'nin (Base Class Library) int gibi primitive tipler için comparer çağrısı yapmayan özelleşmiş bir yolu var. Ölçümler makinede başka işler çalışırken alındı; oranlara bak.

Stability: Eşit Element'lerin Sırası

Bir sorting algoritması, karşılaştırmaya göre eşit olan element'lerin girdideki sırasını koruyorsa stable'dır. Sayıları sıralarken bunun bir önemi yok; bir 5'i diğerinden ayıramazsın. Object'leri bir alana göre sıralarken ise öbür alanların sırası tam olarak bu özelliğe bağlı. Açılıştaki senaryoyu çalıştıralım: 200 sipariş tarihe göre sıralı geliyor, önce Array.Sort ile, sonra merge sort ile müşteriye göre sıralıyoruz:

Array.Sort by customer (first 5 orders of 'ada'):
  #200 ada    2026-12-06
  # 29 ada    2026-10-10
  #140 ada    2026-11-16
  #136 ada    2026-11-15
  #132 ada    2026-11-14
MergeSort by customer (first 5 orders of 'ada'):
  #  8 ada    2026-10-03
  #  9 ada    2026-10-04
  # 29 ada    2026-10-10
  # 33 ada    2026-10-12
  # 41 ada    2026-10-14

Açılıştaki varsayım yanlış. Array.Sort Ada'nın siparişlerini bir arada topladı ama aralarındaki tarih sırası kayboldu: aralık ayındaki sipariş ilk sırada. Microsoft Learn bunu açıkça yazıyor: Array.Sort unstable bir sıralama yapıyor ve eşit element'lerin sırası korunmayabiliyor; List<T>.Sort da aynı algoritmayı kullanıyor. Merge sort'ta ise birleştirmedeki <= eşitlikte soldaki element'i önce alıyor ve tarih sırası korunuyor. LINQ'teki (Language Integrated Query) OrderBy ve ThenBy stable, dokümanı da bunu garanti ediyor. Testler üç stable yolu ve unstable olanı aynı veriyle sabitliyor:

private static readonly Comparer<Order> ByCustomer = Comparer<Order>.Create((a, b) => string.CompareOrdinal(a.Customer, b.Customer));

private static bool DatesInOrderWithinCustomer(IReadOnlyList<Order> sorted) =>
    sorted.Zip(sorted.Skip(1)).All(p => p.First.Customer != p.Second.Customer || p.First.Date <= p.Second.Date);

[Fact]
public void ArraySort_ByCustomer_LosesDateOrder()
{
    Order[] orders = SampleOrders.Create(200); // tarihe göre sıralı geliyor

    Array.Sort(orders, ByCustomer);

    Assert.False(DatesInOrderWithinCustomer(orders));
}

[Fact]
public void StableSorts_ByCustomer_KeepDateOrder()
{
    Order[] merge = SampleOrders.Create(200);
    MergeSort.TopDown(merge, ByCustomer);
    Order[] insertion = SampleOrders.Create(200);
    SimpleSorts.InsertionSort<Order>(insertion, ByCustomer);
    List<Order> linq = [.. SampleOrders.Create(200).OrderBy(o => o.Customer, StringComparer.Ordinal)];

    Assert.True(DatesInOrderWithinCustomer(merge));
    Assert.True(DatesInOrderWithinCustomer(insertion));
    Assert.True(DatesInOrderWithinCustomer(linq));
    Assert.Equal(linq, merge);
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.SortingTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (604ms)

Test run summary: Passed!
  total: 7
  failed: 0
  succeeded: 7

Bu hatanın sinsi tarafı küçük veride görünmemesi. 16 veya daha az siparişte Array.Sort insertion sort kullanıyor ve insertion sort stable olduğu için sıra korunuyor; test ortamındaki 10 siparişlik müşteri listesi doğru görünüyor, production'daki 200 siparişlik liste bozuluyor. Test verisini bu yüzden 200 elemanlı seçtik.

Doğru çözüm iki seçenekten biri: sıralamanın bütün kriterlerini açıkça söylemek (OrderBy(o => o.Customer).ThenBy(o => o.Date) ya da iki alanı birden karşılaştıran bir comparer) veya stable bir sıralamaya güvenmek. Birincisi daha sağlam; kodu okuyan biri sıranın neye göre olduğunu görüyor ve girdinin sırasına güvenmiyor. Comparer'ın tutarlı ve transitive olması gerektiği C# Koleksiyonlar serisinin "C# Sıralı Collection'lar: SortedList, SortedDictionary, SortedSet ve IComparer" yazısında anlatıldı.

Üretimde Dikkat

Kendi sorting algoritmanı production'a koyma. Array.Sort, List<T>.Sort, MemoryExtensions.Sort ve LINQ'in Order/OrderBy'ı yıllardır optimize ediliyor. Bu yazıdaki algoritmaların asıl değeri hangi durumda hangisini seçeceğini bilmek: stability gerekiyorsa LINQ ya da açık çok alanlı bir comparer, bellekten büyük veri varsa external merge sort ya da veritabanı.

LINQ'in stable sıralamasının bir bedeli var: OrderBy yeni bir sequence üretiyor ve key'leri ayrı bir array'de tutuyor; yerinde sıralama yapan Array.Sort'tan daha fazla bellek ayırıyor. Sıcak bir yolda büyük bir listeyi her istekte sıralıyorsan farkı ölç.

Neredeyse sıralı veriye özel durum olarak bak. Sürekli küçük değişikliklerle güncellenen bir sıralı liste (fiyat güncellemeleri, skor tablosu) her seferinde baştan sıralanmak yerine değişen element'i doğru yere taşıyarak (tek bir insertion sort adımı ya da BinarySearch + Insert) güncellenebilir.

Sık Düşülen Tuzaklar

Array.Sort'un stable olduğunu varsaymak. Test verisi 16 elemandan küçükse hata görünmüyor; production verisinde sıra rastgele bozuluyor. Eşit key'li element'lerin sırası önemliyse ya bütün kriterleri comparer'a yaz ya da OrderBy/ThenBy kullan.

Merge'de <= yerine < yazmak. Eşitlikte sağdaki element'i önce almak merge sort'u sessizce unstable yapar. Sonuç hâlâ sıralı olduğu için sıradan bir sorting testi bunu yakalamaz; ayrı bir stability testi gerekiyor.

Insertion sort'ta katı olmayan karşılaştırma. > yerine >= eşit element'leri de kaydırır ve stability'yi bozar.

Büyük veride merge sort'un belleğini unutmak. 100 milyon long'u merge sort ile sıralamak 800 MB'lık ikinci bir buffer istiyor; container'ın bellek sınırını bu tür ek bellek aşar.

Küçük Bir Deneme

★☆☆ Merge'deki <='i < yap ve testleri çalıştır. Hangi test kırılıyor, hangisi geçmeye devam ediyor? Bu, stability'nin neden ayrı test edilmesi gerektiğini gösteriyor mu?

★★☆ Merge sort'a "küçük alt array'lerde insertion sort'a geç" optimizasyonu ekle: hi - lo <= 16 olduğunda InsertionSort çağır. Benchmark'taki rastgele girdi süresi nasıl değişiyor? Eşik değerini 8 ve 32 ile de dene.

★★★ Belleğe sığmayan veriyi simüle et: 1.000.000 rastgele siparişi 10 dosyaya böl, her dosyayı ayrı sırala, sonra 10 dosyayı aynı anda okuyan bir k-way merge ile tek bir sıralı dosya üret. Her adımda en küçük başı seçmek için şimdilik basit bir döngü kullan; serinin heap yazısında bunu PriorityQueue ile değiştireceğiz.

Merge sort her durumda n log n ama ek bellek istiyor. Bir sonraki yazıda yerinde sıralayan ve pratikte genelde en hızlı olan quick sort'a, kötü girdide O(n²)'ye düşmesini engelleyen introsort'a ve karşılaştırma yapmadan sıralayan counting ve radix sort'a bakıyoruz: .NET'in Array.Sort'u tam olarak nasıl sıralıyor?