ExternalMergeSorter.cs

using System;
using System.Collections.Generic;

namespace Algorithms.Sorters.External;

public class ExternalMergeSorter<T> : IExternalSorter<T>
{
    public void Sort(
        ISequentialStorage<T> mainMemory,
        ISequentialStorage<T> temporaryMemory,
        IComparer<T> comparer)
    {
        var originalSource = mainMemory;
        var source = mainMemory;
        var temp = temporaryMemory;
        var totalLength = mainMemory.Length;
        for (var stripLength = 1L; stripLength < totalLength; stripLength *= 2)
        {
            using var left = source.GetReader();
            using var right = source.GetReader();
            using var output = temp.GetWriter();

            for (var i = 0L; i < stripLength; i++)
            {
                right.Read();
            }

            Merge(left, right, output, stripLength, Math.Min(stripLength, totalLength - stripLength), comparer);
            var step = 2 * stripLength;
            long rightStripStart;
            for (rightStripStart = stripLength + step; rightStripStart < mainMemory.Length; rightStripStart += step)
            {
                for (var i = 0L; i < stripLength; i++)
                {
                    left.Read();
                    right.Read();
                }

                Merge(
                    left,
                    right,
                    output,
                    stripLength,
                    Math.Min(stripLength, totalLength - rightStripStart),
                    comparer);
            }

            for (var i = 0L; i < totalLength + stripLength - rightStripStart; i++)
            {
                output.Write(right.Read());
            }

            (source, temp) = (temp, source);
        }

        if (source == originalSource)
        {
            return;
        }

        using var sorted = source.GetReader();
        using var dest = originalSource.GetWriter();
        for (var i = 0; i < totalLength; i++)
        {
            dest.Write(sorted.Read());
        }
    }

    private static void Merge(
        ISequentialStorageReader<T> left,
        ISequentialStorageReader<T> right,
        ISequentialStorageWriter<T> output,
        long leftLength,
        long rightLength,
        IComparer<T> comparer)
    {
        var leftIndex = 0L;
        var rightIndex = 0L;

        var l = left.Read();
        var r = right.Read();
        while (true)
        {
            if (comparer.Compare(l, r) < 0)
            {
                output.Write(l);
                leftIndex++;
                if (leftIndex == leftLength)
                {
                    break;
                }

                l = left.Read();
            }
            else
            {
                output.Write(r);
                rightIndex++;
                if (rightIndex == rightLength)
                {
                    break;
                }

                r = right.Read();
            }
        }

        if (leftIndex < leftLength)
        {
            output.Write(l);
            Copy(left, output, leftLength - leftIndex - 1);
        }

        if (rightIndex < rightLength)
        {
            output.Write(r);
            Copy(right, output, rightLength - rightIndex - 1);
        }
    }

    private static void Copy(ISequentialStorageReader<T> from, ISequentialStorageWriter<T> to, long count)
    {
        for (var i = 0; i < count; i++)
        {
            to.Write(from.Read());
        }
    }
}