public static IList<T> BubbleSort<T>(this IList<T> collection) where T : IComparable
{
    for (var i = 0; i < collection.Count; i++)
    {
        for (var j = i + 1; j < collection.Count; j++)
        {
            if (collection[i].CompareTo(collection[j]) > 0) // Сортировка по возрастанию
            {
                (collection[j], collection[i]) = (collection[i], collection[j]);
            }
        }
    }

    return collection;
}

public static IList<T> InsertionSort<T>(this IList<T> collection) where T : IComparable
{
    for (var i = 1; i < collection.Count; i++)
    {
        var item = collection[i];
        var j = i - 1;

        while (j >= 0 && collection[j].CompareTo(item) > 0) // Сортировка по возрастанию
        {
            collection[j + 1] = collection[j];
            j--;
        }

        collection[j + 1] = item;
    }

    return collection;
}

public static IList<T> SelectionSort<T>(this IList<T> collection) where T : IComparable
{
    for (var i = 0; i < collection.Count - 1; i++)
    {
        var index = i;
        for (var j = i + 1; j < collection.Count; j++)
        {
            if (collection[index].CompareTo(collection[j]) > 0) // Сортировка по возрастанию
            {
                index = j;
            }
        }

        (collection[index], collection[i]) = (collection[i], collection[index]);
    }

    return collection;
}

public static IList<T> CocktailSort<T>(this IList<T> collection) where T : IComparable
{
    for (var i = 0; i < collection.Count; i++)
    {
        var needSort = false;
        for (var j = i; j < collection.Count - 1 - i; j++)
        {
            if (collection[j].CompareTo(collection[j + 1]) > 0) // Сортировка по возрастанию
            {
                (collection[j], collection[j + 1]) = (collection[j + 1], collection[j]);
                needSort = true;
            }
        }

        for (var j = collection.Count - 2 - i; j > i; j--)
        {
            if (collection[j - 1].CompareTo(collection[j]) > 0) // Сортировка по возрастанию
            {
                (collection[j], collection[j - 1]) = (collection[j - 1], collection[j]);
                needSort = true;
            }
        }

        if (!needSort) return collection;
    }

    return collection;
}

public static IList<T> ShellSort<T>(this IList<T> collection) where T : IComparable
{
    var step = collection.Count / 2;
    while (step > 0)
    {
        step /= 2;
        for (var i = step; i < collection.Count; i++)
        {
            var j = i;
            while (j >= step && collection[j - step].CompareTo(collection[j]) > 0) // Сортировка по возрастанию
            {
                (collection[j], collection[j - step]) = (collection[j - step], collection[j]);
                j -= step;
            }
        }
    }

    return collection;
}

private static int BinarySearchRecursive<T>(this IList<T> collection, T key, int left, int right) where T : IComparable
{
    if (right < left) throw new ArgumentOutOfRangeException("Левая / правая граница указана неправильно.");

    var mid = left + (right - left) / 2; // ! вычислять нужно именно так
    var value = collection[mid];

    if (key.Equals(value)) return mid;

    return value.CompareTo(key) > 0 // Коллекция отсортирована по возрастанию
        ? collection.BinarySearchRecursive(key, left, mid - 1)
        : collection.BinarySearchRecursive(key, mid + 1, right);
}

private static int BinarySearchIterative<T>(this IList<T> collection, T key, int left, int right) where T : IComparable
{
    while (left <= right)
    {
        var mid = left + (right - left) / 2; // ! вычислять нужно именно так
        var value = collection[mid];

        if (key.Equals(value)) return mid;

        if (value.CompareTo(key) > 0) // Коллекция отсортирована по возрастанию
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    throw new ArgumentOutOfRangeException("Левая / правая граница указана неправильно.");
}

private static IList<T> QuickSortLomuto<T>(this IList<T> collection, int left, int right) where T : IComparable
{
    if (left >= right) return collection;
    var pivot = collection.PartitionLomuto(left, right);
    QuickSortLomuto(collection, left, pivot - 1);
    QuickSortLomuto(collection, pivot + 1, right);

    return collection;
}

private static int PartitionLomuto<T>(this IList<T> collection, int left, int right) where T : IComparable
{
    var pivot = left - 1; // В качестве опорного элемента выбирается самый левый элемент
    for (var i = left; i < right; i++)
    {
        if (collection[right].CompareTo(collection[i]) > 0) // Сортировка по возрастанию
        {
            pivot++;
            (collection[pivot], collection[i]) = (collection[i], collection[pivot]);
        }
    }

    pivot++;
    (collection[pivot], collection[right]) = (collection[right], collection[pivot]);

    return pivot;
}

private static IList<T> QuickSortHoare<T>(this IList<T> collection, int left, int right) where T : IComparable
{
    if (left < right)
    {
        var pivot = collection.PartitionHoare(left, right);
        collection.QuickSortHoare(left, pivot);
        collection.QuickSortHoare(pivot + 1, right);
    }

    return collection;
}

private static int PartitionHoare<T>(this IList<T> collection, int left, int right) where T : IComparable
{
    var pivot = collection[left]; // В качестве опорного элемента выбирается самый левый элемент

    var i = left - 1;
    var j = right + 1;

    while (true)
    {
        do
        {
            i++;
        } while (pivot.CompareTo(collection[i]) > 0); // Сортировка по возрастанию

        do
        {
            j--;
        } while (collection[j].CompareTo(pivot) > 0); // Сортировка по возрастанию

        if (i >= j)
        {
            return j;
        }

        (collection[i], collection[j]) = (collection[j], collection[i]);
    }
}

public class DirectMergeSorter
{
    public string InputFilePath { get; set; }

    public string OutputFilePath { get; set; } = "sorted.csv";

    public int SortKey { get; set; }

    private long _seriesLength;

    private long _countSegments;

    private const string AuxiliaryFilePathA = "A.csv";

    private const string AuxiliaryFilePathB = "B.csv";

    private readonly Func<double, double, bool> _ascending = (x, y) => x < y; // Сортировка по возрастанию

    private readonly Func<double, double, bool> _descending = (x, y) => x < y; // Сортировка по убыванию

    public DirectMergeSorter(string filePath = "unsorted.csv", int sortKey = 0)
    {
        InputFilePath = filePath;
        SortKey = sortKey;
        _seriesLength = 1;
    }

    public void Sort() => Sort(_ascending);

    public void SortDescending() => Sort(_descending);

    private void Sort(Func<double, double, bool> order)
    {
        var index = 1;
        while (true)
        {
            SplitToFiles();

            if (_countSegments == 1) break;

            Merge(order);
        }
    }

    private static int GetCountLinesFile(string filePath)
    {
        using var sr = new StreamReader(filePath);
        var count = 0;
        while ((sr.ReadLine()) != null)
        {
            count++;
        }

        return count;
    }

    private void SplitToFiles()
    {
        _countSegments = 1;

        using var sr = _seriesLength == 1 ? new StreamReader(InputFilePath) : new StreamReader(OutputFilePath);

        using var swA = new StreamWriter(AuxiliaryFilePathA);
        using var swB = new StreamWriter(AuxiliaryFilePathB);

        var counter = 0L;
        var isFirstFile = true;

        var length = GetCountLinesFile(_seriesLength == 1 ? InputFilePath : OutputFilePath);
        var position = 0L;

        while (position != length)
        {
            if (counter == _seriesLength)
            {
                isFirstFile = !isFirstFile;
                counter = 0;
                _countSegments++;
            }

            var str = sr.ReadLine();

            position++;

            if (isFirstFile)
            {
                swA.WriteLine(str);
            }
            else
            {
                swB.WriteLine(str);
            }

            counter++;
        }
    }

    private void Merge(Func<double, double, bool> comparer)
    {
        using var srA = new StreamReader(AuxiliaryFilePathA);
        using var srB = new StreamReader(AuxiliaryFilePathB);

        using var sw = new StreamWriter(OutputFilePath);

        var counterA = _seriesLength; 
        var counterB = _seriesLength;

        var strA = "";
        var strB = "";

        var isPickedA = false;
        var isPickedB = false;
        var isEndA = false;
        var isEndB = false;

        var lengthA = GetCountLinesFile(AuxiliaryFilePathA);
        var lengthB = GetCountLinesFile(AuxiliaryFilePathB);

        var positionA = 0L;
        var positionB = 0L;

        while (!isEndA || !isEndB)
        {
            if (counterA == 0 && counterB == 0)
            {
                counterA = _seriesLength;
                counterB = _seriesLength;
            }

            if (positionA != lengthA)
            {
                if (counterA > 0 && !isPickedA)
                {
                    strA = srA.ReadLine();
                    positionA++;
                    isPickedA = true;
                }
            }
            else
            {
                isEndA = true;
            }

            if (positionB != lengthB)
            {
                if (counterB > 0 && !isPickedB)
                {
                    strB = srB.ReadLine();
                    positionB++;
                    isPickedB = true;
                }
            }
            else
            {
                isEndB = true;
            }

            if (isPickedA)
            {
                if (isPickedB)
                {
                    if (comparer(double.Parse(strA.Split(";")[SortKey], CultureInfo.InvariantCulture), double.Parse(strB.Split(";")[SortKey], CultureInfo.InvariantCulture)))
                    {
                        sw.WriteLine(strA);
                        counterA--;
                        isPickedA = false;
                    }
                    else
                    {
                        sw.WriteLine(strB);
                        counterB--;
                        isPickedB = false;
                    }
                }
                else
                {
                    sw.WriteLine(strA);
                    counterA--;
                    isPickedA = false;
                }
            }
            else if (isPickedB)
            {
                sw.WriteLine(strB);
                counterB--;
                isPickedB = false;
            }
        }

        _seriesLength *= 2;
    }
}

public class NaturalMergeSorter
{
    public string InputFilePath { get; set; }

    public string OutputFilePath { get; set; } = "sorted.csv";

    public int SortKey { get; set; }

    private bool _isPassageFirst = true;

    private long _countSegments;

    private const string AuxiliaryFilePathA = "A.csv";

    private const string AuxiliaryFilePathB = "B.csv";

    private readonly Func<double, double, bool> _ascending = (x, y) => x < y; // Сортировка по возрастанию

    private readonly Func<double, double, bool> _descending = (x, y) => x < y; // Сортировка по убыванию

    public NaturalMergeSorter(string filePath = "unsorted.csv", int sortKey = 0)
    {
        InputFilePath = filePath;
        SortKey = sortKey;
    }

    public void Sort() => Sort(_ascending);

    public void SortDescending() => Sort(_descending);

    private void Sort(Func<double, double, bool> order)
    {
        var index = 1;
        while (true)
        {
            SplitToFiles(order);

            if (_countSegments == 1) break;

            Merge(order);
        }
    }

    private static int GetCountLinesFile(string filePath)
    {
        using var sr = new StreamReader(filePath);
        var count = 0;
        while (sr.ReadLine() != null)
        {
            count++;
        }

        return count;
    }

    private void SplitToFiles(Func<double, double, bool> comparer)
    {
        _countSegments = 1;

        using var sr = _isPassageFirst ? new StreamReader(InputFilePath) : new StreamReader(OutputFilePath);

        using var swA = new StreamWriter(AuxiliaryFilePathA);
        using var swB = new StreamWriter(AuxiliaryFilePathB);

        var isStart = false;
        var isFirstFile = true;

        var length = GetCountLinesFile(_isPassageFirst ? InputFilePath : OutputFilePath);
        _isPassageFirst = false;
        var position = 0L;

        var str = "";
        var nextStr = "";

        if (length == 1)
        {
            swA.WriteLine(sr.ReadLine());
            return;
        }

        while (position != length)
        {
            if (!isStart)
            {
                str = sr.ReadLine();
                position++;

                swA.WriteLine(str);
                isStart = true;
            }

            nextStr = sr.ReadLine();

            position++;

            if (comparer(double.Parse(nextStr.Split(";")[SortKey], CultureInfo.InvariantCulture), double.Parse(str.Split(";")[SortKey], CultureInfo.InvariantCulture)))
            {
                isFirstFile = !isFirstFile;
                _countSegments++;
            }

            if (isFirstFile)
            {
                swA.WriteLine(nextStr);
            }
            else
            {
                swB.WriteLine(nextStr);
            }

            str = nextStr;
        }
    }

    private void Merge(Func<double, double, bool> comparer)
    {
        using var srA = new StreamReader(AuxiliaryFilePathA);
        using var srB = new StreamReader(AuxiliaryFilePathB);

        using var sw = new StreamWriter(OutputFilePath);

        var strA = "";
        var strB = "";

        var isPickedA = false;
        var isPickedB = false;
        var isEndA = false;
        var isEndB = false;

        var lengthA = GetCountLinesFile(AuxiliaryFilePathA);
        var lengthB = GetCountLinesFile(AuxiliaryFilePathB);

        var positionA = 0L;
        var positionB = 0L;

        while (!isEndA || !isEndB || isPickedA || isPickedB)
        {
            isEndA = positionA == lengthA;
            isEndB = positionB == lengthB;

            if (!isEndA && !isPickedA)
            {
                strA = srA.ReadLine();

                positionA++;
                isPickedA = true;
            }

            if (!isEndB && !isPickedB)
            {
                strB = srB.ReadLine();

                positionB++;
                isPickedB = true;
            }

            if (isPickedA)
            {
                if (isPickedB)
                {
                    if (comparer(double.Parse(strA.Split(";")[SortKey], CultureInfo.InvariantCulture),
                            double.Parse(strB.Split(";")[SortKey], CultureInfo.InvariantCulture)))
                    {
                        sw.WriteLine(strA);
                        isPickedA = false;
                    }
                    else
                    {
                        sw.WriteLine(strB);
                        isPickedB = false;
                    }
                }
                else
                {
                    sw.WriteLine(strA);
                    isPickedA = false;
                }
            } else if (isPickedB)
            {
                sw.WriteLine(strB);
                isPickedB = false;
            }
        }
    }
}

public class MultiWayMergeSorter
{
    private class HeadIndexPair
    {
        public string? Head { get; }
        public int Index { get; }

        public HeadIndexPair(string? head, int index)
        {
            Head = head;
            Index = index;
        }
    }

    public string InputFilePath { get; set; }

    public  string OutputFilePath { get; set; } = "sorted.csv";

    public int SortKey { get; set; }

    public int CountChunkRows { get; set; }

    public string ColumnSeparator { get; set; }

    private const string TmpFilePrefix = "tmpFile";
    private int _numChunk;

    public MultiWayMergeSorter(string inputFilePath = "unsorted.csv", int countChunkRows = 10, int sortKey = 0, string columnSeparator = ";")
    {
        InputFilePath = inputFilePath;
        CountChunkRows = countChunkRows;
        SortKey = sortKey;
        ColumnSeparator = columnSeparator;
    }

    public void Sort()
    {
        using var sr = new StreamReader(InputFilePath);
        var cnt = 0;

        var chunk = new string[CountChunkRows];

        string? line;
        while ((line = sr.ReadLine()) != null)
        {
            chunk[cnt] = line;
            cnt++;
            if (cnt % CountChunkRows == 0)
            {
                SortAndSaveChunk(chunk, TmpFilePrefix + _numChunk);
                cnt = 0;
                _numChunk++;
            }
        }

        if (cnt != 0)
        {
            SortAndSaveChunk(chunk, TmpFilePrefix + _numChunk);
            _numChunk++;
        }

        var readers = new StreamReader[_numChunk];

        var heads = new PriorityQueue<HeadIndexPair, HeadIndexPair>(Comparer<HeadIndexPair>.Create((a, b) => Compare(a.Head, b.Head)));

        for (var i = 0; i < _numChunk; i++)
        {
            var strRead = new StreamReader(TmpFilePrefix + i);
            readers[i] = strRead;
        }

        using (var streamOut = new StreamWriter(OutputFilePath))
        {
            for (var i = 0; i < _numChunk; i++)
            {
                heads.Enqueue(new HeadIndexPair(readers[i].ReadLine(), i), new HeadIndexPair(readers[i].ReadLine(), i));
            }

            while (true)
            {
                var minH = heads.Count > 0 ? heads.Dequeue() : null;
                if (null == minH) break;

                streamOut.WriteLine(minH.Head);

                if ((line = readers[minH.Index].ReadLine()) != null)
                    heads.Enqueue(new HeadIndexPair(line, minH.Index), new HeadIndexPair(line, minH.Index));
            }

            for (var i = 0; i < _numChunk; i++)
            {
                readers[i].Close();
            }
                    
        }

        sr.Close();
    }

    private void SortAndSaveChunk(string?[] chunk, string filename)
    {
        Array.Sort(chunk, Compare);
        using var sw = new StreamWriter(filename);
        foreach (var t in chunk)
        {
            if (t != null) sw.WriteLine(t);
        }

        sw.Close();
    }

    private string ExtractCol(string line)
    {
        var columns = line.Split(ColumnSeparator);
        return columns[SortKey];
    }

    private int Compare(string? a, string? b)
    {
        if (a == null && b == null) return 0;
        if (a == null) return 1;
        if (b == null) return -1;
        return string.Compare(ExtractCol(a), ExtractCol(b), StringComparison.Ordinal);
    }
}

public class Node<T> where T : IComparable
{
    public T Value { get; set; }

    public Node<T>? Left { get; private set; }

    public Node<T>? Right { get; private set; }

    public Node(T value)
    {
        Value = value;
    }

    public void Insert(T value)
    {
        if (Value.CompareTo(value) > 0) // Сортировка по возрастанию
        {
            if (Left == null)
            {
                Left = new Node<T>(value);
            }
            else
            {
                Left.Insert(value);
            }
        }
        else
        {
            if (Right == null)
            {
                Right = new Node<T>(value);
            }
            else
            {
                Right.Insert(value);
            }
        }
    }

    public IList<T> ToList(IList<T>? collection = null)
    {
        var index = 0;
        return ToList(ref index, collection);
    }

    private IList<T> ToList(ref int index, IList<T>? collection = null)
    {
        collection ??= new List<T>();

        Left?.ToList(ref index, collection);

        collection[index++] = Value;

        Right?.ToList(ref index, collection);

        return collection;
    }
}

public static IList<T> TreeSort<T>(this IList<T> collection) where T : IComparable
{
    if (collection.Count > 0)
    {
        var node = new Node<T>(collection[0]);
        for (var i = 1; i < collection.Count; i++)
        {
            node.Insert(collection[i]);
        }

        node.ToList(collection);
    }

    return collection;
}

public static IList<int> RadixSort(this IList<int> collection)
{
    var maxValue = collection.Max();

    for (var exponent = 1; maxValue / exponent > 0; exponent *= 10)
    {
        collection.CountingSort(exponent);
    }

    return collection;
}

public static IList<int> CountingSort(this IList<int> collection, int exponent)
{
    var outputArr = new int[collection.Count];
    var countArr = new int[10];

    foreach (var item in collection) // Считаем количество вхождений каждого элемента массива
    {
        countArr[(item / exponent) % 10]++;
    }

    for (var i = 1; i < 10; i++) // Сохраняем фактические позиции элементов
    {
        countArr[i] += countArr[i - 1];
    }

    for (var i = collection.Count - 1; i >= 0; i--) // Устанавливаем элементы в отсортированные позиции
    {
        outputArr[countArr[(collection[i] / exponent) % 10] - 1] = collection[i];
        countArr[(collection[i] / exponent) % 10]--;
    }

    for (var i = 0; i < collection.Count; i++) // Копируем элементы в исходный массив
    {
        collection[i] = outputArr[i];
    }

    return collection;
}

/// <summary> Словарь: хеш-таблица, разрешение коллизий методом цепочек </summary>
/// <typeparam name="TKey"> Тип ключа </typeparam>
/// <typeparam name="TValue"> Тип значения </typeparam>
public class Dictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
{
    private readonly int _size;

    public double FillFactor => (double)Count / _size;

    public int MaxLengthChain => _items.Max(x => x?.Count ?? 0);

    public int MinLengthChain => _items.Min(x => x?.Count ?? 0);

    public IEnumerable<int> LengthsChains => _items.Select(x => x?.Count ?? 0);

    public int Count { get; private set; }

    private readonly LinkedList<KeyValuePair<TKey, TValue?>>?[] _items;

    public Dictionary(int size = 1000)
    {
        if (!IsSizeCorrect(size)) throw new AggregateException(nameof(size));
        _size = size;
        _items = new LinkedList<KeyValuePair<TKey, TValue?>>[size];
    }

    public void Add(TKey key, TValue value)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));
        var item = new KeyValuePair<TKey, TValue?>(key, value);
        Insert(item);
    }

    protected void Insert(KeyValuePair<TKey, TValue?> item)
    {
        var position = GetListPosition(item.Key);
        var linkedList = GetLinkedList(position);

        foreach (var pair in linkedList)
        {
            if (pair.Key != null && pair.Key.Equals(item.Key))
                throw new ArgumentException("Элемент по указанному ключу уже существует.");
        }

        linkedList.AddLast(item);
        Count++;
    }

    protected bool IsSizeCorrect(int size)
    {
        return size > 0;
    }

    public bool Remove(TKey key)
    {
        var position = GetListPosition(key);
        var linkedList = GetLinkedList(position);
        var itemFound = false;
        var foundItem = default(KeyValuePair<TKey, TValue?>);
        foreach (var item in linkedList)
        {
            if (item.Key != null && item.Key.Equals(key))
            {
                itemFound = true;
                foundItem = item;
            }
        }

        if (itemFound)
        {
            linkedList.Remove(foundItem);
            Count--;
        }
        return itemFound;
    }

    public bool ContainsKey(TKey key)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));
        var position = GetListPosition(key);
        var linkedList = GetLinkedList(position);

        var foundItem = false;
        foreach (var item in linkedList)
        {
            if (item.Key != null && item.Key.Equals(key))
            {
                foundItem = true;
                break;
            }
        }

        return foundItem;
    }

    public TValue? GetValue(TKey key)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));
        var position = GetListPosition(key);
        var linkedList = GetLinkedList(position);
        foreach (var item in linkedList)
        {
            if (item.Key != null && item.Key.Equals(key)) return item.Value;
        }

        return default;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        var t = GetValue(key);
        value = t;
        return t != null;
    }

    protected int GetListPosition(TKey key)
    {

        return Math.Abs(key.GetHashCode() % _size); // Метод деления

        // Метод умножения
        // var goldenRatioConst = (Math.Sqrt(5) - 1) / 2;
        // return (int) Math.Abs(_size * (key.GetHashCode() * goldenRatioConst % 1));
    }

    protected LinkedList<KeyValuePair<TKey, TValue?>> GetLinkedList(int position)
    {
        var linkedList = _items[position];
        if (linkedList == null)
        {
            linkedList = new LinkedList<KeyValuePair<TKey, TValue?>>();
            _items[position] = linkedList;
        }

        return linkedList;
    }

    public void Clear()
    {
        if (Count > 0)
        {
            for (var i = 0; i < _items.Length; i++)
            {
                _items[i] = null;
            }
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue?>> GetEnumerator()
    {
        foreach (var linkedList in _items)
        {
            if (linkedList != null)
            {
                foreach (var keyValuePair in linkedList)
                {
                    yield return keyValuePair;
                }
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

/// <summary> Хеш-таблица, разрешение коллизий методом открытой адресации </summary>
/// <typeparam name="TKey"> Тип ключа </typeparam>
/// <typeparam name="TValue"> Тип значения </typeparam>
public class Hashtable<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
{
    private readonly int _size;

    private readonly KeyValuePair<TKey, TValue?>[] _items;

    private readonly bool[] _removed;

    private static readonly Func<Func<object, int, int>, object, int, int, int> LinearHashing =
        (f, key, sizeHashTable, index) => (f(key, sizeHashTable) + index) % sizeHashTable;

    private static readonly Func<Func<object, int, int>, object, int, int, int> QuadraticHashing =
        (f, key, sizeHashTable, index) => (f(key, sizeHashTable) + (int)Math.Pow(index, 2)) % sizeHashTable;

    private static readonly Func<Func<object, int, int>, Func<object, int, int>, object, int, int, int> DoubleHashing =
        (f1, f2, key, sizeHashTable, index) => (f1(key, sizeHashTable) + index * f2(key, sizeHashTable)) % sizeHashTable;

    public int Count { get; private set; }

    public int MaxClusterLength
    {
        get
        {
            var max = 0;
            var current = 0;
            foreach (var item in _items)
            {
                if (!item.Equals(default(KeyValuePair<TKey, TValue?>)))
                {
                    current++;
                }
                else
                {
                    max = Math.Max(max, current);
                    current = 0;
                }
            }

            return Math.Max(max, current);
        }
    }

    public Hashtable(int size = 1000)
    {
        if (!IsSizeCorrect(size)) throw new AggregateException(nameof(size));
        _size = size;
        _items = new KeyValuePair<TKey, TValue?>[size];
        _removed = new bool[_size];
    }

    protected bool CheckOpenSpace()
    {
        var isOpen = false;
        for (var i = 0; i < _size; i++)
        {
            if (_items[i].Equals(default(KeyValuePair<TKey, TValue?>))) isOpen = true;
        }

        return isOpen;
    }

    protected bool IsSizeCorrect(int size)
    {
        return size > 0;
    }

    protected bool CheckUniqueKey(TKey key)
    {
        foreach (var item in _items)
        {
            if (item.Key != null && item.Key.Equals(key)) return false;
        }

        return true;
    }

    public void Add(TKey key, TValue value)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        if (!CheckOpenSpace()) throw new ArgumentOutOfRangeException("Хеш-таблица переполнена.");

        if (!CheckUniqueKey(key)) throw new ArgumentException("Элемент по указанному ключу уже существует.");

        Insert(key, value);
    }

    protected void Insert(TKey key, TValue value)
    {
        var index = 0;
        var hashCode = GetHash(key, index);

        while (!_items[hashCode].Equals(default(KeyValuePair<TKey, TValue>)) && !_items[hashCode].Key.Equals(key))
        {
            index++;
            hashCode = GetHash(key, index);
        }

        _items[hashCode] = new KeyValuePair<TKey, TValue?>(key, value);
        _removed[hashCode] = false;
        Count++;
    }

    protected int GetHash(TKey key, int index)
    {
        // Линейный анализ, вспомогательная функция — метод деления.
        return LinearHashing((key, sizeHashTable) => Math.Abs(key.GetHashCode() % sizeHashTable), key, _size, index);
    }

    public TValue? GetValue(TKey key)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        var index = 0;
        var hashCode = GetHash(key, index);

        while ((!_items[hashCode].Equals(default(KeyValuePair<TKey, TValue>)) || _removed[hashCode]) && !_items[hashCode].Key.Equals(key))
        {
            index++;
            hashCode = GetHash(key, index);
        }

        return _items[hashCode].Value;
    }

    public bool Remove(TKey key)
    {
        var index = 0;
        var hashCode = GetHash(key, index);

        while ((!_items[hashCode].Equals(default(KeyValuePair<TKey, TValue>)) || _removed[hashCode]) && !_items[hashCode].Key.Equals(key))
        {
            index++;
            hashCode = GetHash(key, index);
        }

        if (_items[hashCode].Equals(default(KeyValuePair<TKey, TValue>)))
        {
            return false;
        }
        else
        {
            _items[hashCode] = default;
            _removed[hashCode] = true;
            Count--;
            return true;
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue?>> GetEnumerator()
    {
        foreach (var keyValuePair in _items)
        {
            if (!keyValuePair.Equals(default(KeyValuePair<TKey, TValue?>)))
            {
                yield return keyValuePair;
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

private static IList<string> ABCSort(this IList<string> collection, int rank)
{
    if (collection.Count < 2) return collection;

    var table = new System.Collections.Generic.Dictionary<char, IList<string>>(); // key - символ в позиции rank, список слов с символом key в позиции rank
    var listResult = new List<string>();
    var shortWordsCounter = 0;

    foreach (var str in collection)
    {
        if (rank < str.Length)
        {
            if (table.ContainsKey(str[rank]))
            {
                table[str[rank]].Add(str);
            }
            else
            {
                table.Add(str[rank], new List<string> {str});
            }
        }
        else
        {
            listResult.Add(str);
            shortWordsCounter++;
        }
    }

    if (shortWordsCounter == collection.Count) return collection;

    for (var i = 'A'; i <= 'z'; i++)
    {
        if (table.ContainsKey(i))
        {
            foreach (var str in ABCSort(table[i], rank + 1))
            {
                listResult.Add(str);
            }
        }
    }

    return listResult;
}

public class Stack<T> : IReadOnlyCollection<T>
{
    private class Node<T>
    {
        public T Value { get; }

        public Node<T> Top { get; init; }

        public Node(T value)
        {
            Value = value;
        }
    }

    private Node<T>? _top;

    public int Count { get; private set; }

    public void Push(T element)
    {
        var newNode = new Node<T>(element)
        {
            Top = _top
        };
        _top = newNode;
        Count++;
    }

    public T Pop()
    {
        if (IsEmpty()) throw new InvalidOperationException("Стек пуст, нельзя извлечь элемент.");

        var elem = _top.Value;
        _top = _top.Top;
        Count--;
        return elem;
    }

    public T Peek()
    {
        if (IsEmpty()) throw new InvalidOperationException("Стек пуст, нельзя получить элемент.");

        return _top.Value;
    }

    public bool IsEmpty()
    {
        return _top == null;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var node = _top;
        while (node != null)
        {
            yield return node.Value;
            node = node.Top;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class Queue<T> : IReadOnlyCollection<T>
{
    public class Node<T>
    {
        public Node(T value)
        {
            Value = value;
        }

        public T Value { get; set; }

        public Node<T> Next { get; set; }
    }

    private Node<T>? _head;

    private Node<T>? _tail;

    public int Count { get; private set; }

    public bool IsEmpty() => Count == 0;

    public void Enqueue(T value)
    {
        var node = new Node<T>(value);
        var tempNode = _tail;
        _tail = node;
        if (Count == 0)
        {
            _head = _tail;
        }
        else
        {
            tempNode.Next = _tail;
        }

        Count++;
    }

    public T Dequeue()
    {
        if (Count == 0) throw new InvalidOperationException();
        var output = _head.Value;
        _head = _head.Next;
        Count--;

        return output;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var node = _head;
        while (node != null)
        {
            yield return node.Value;
            node = node.Next;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

/// <summary> Класс подмножество для алгоритма Union-find</summary>
private class Subset<TVertex, TEdge> where TVertex : IComparable where TEdge : IComparable
{
    public  Vertex<TVertex, TEdge>  Parent { get; set; }

    public int Rank { get; set; }
}

/// <summary> Метод выполняющий поиск, сжатия пути </summary>
private static Vertex<TVertex, TEdge> Find<TVertex, TEdge>(IReadOnlyDictionary<Vertex<TVertex, TEdge>, Subset<TVertex, TEdge>> subsets, Vertex<TVertex, TEdge> parent) where TVertex : IComparable where TEdge : IComparable
{
    // Идея: сделать найденный корень родителем 
    if (subsets[parent].Parent != parent)
        subsets[parent].Parent = Find(subsets, subsets[parent].Parent);

    return subsets[parent].Parent;
}

/// <summary> Метод объединения вершин для Union-find </summary>
private static void Union<TVertex, TEdge>(IReadOnlyDictionary<Vertex<TVertex, TEdge>, Subset<TVertex, TEdge>> subsets, Vertex<TVertex, TEdge> vertex1, Vertex<TVertex, TEdge> vertex2) where TVertex : IComparable where TEdge : IComparable
{
    var xRoot = Find(subsets, vertex1);
    var yRoot = Find(subsets, vertex2);

    // Идея: подкреплять дерево меньшей глубины под корень более глубокого дерева
    if (subsets[xRoot].Rank < subsets[yRoot].Rank)
    {
        subsets[xRoot].Parent = yRoot;
    }
    else if (subsets[xRoot].Rank > subsets[yRoot].Rank)
    {
        subsets[yRoot].Parent = xRoot;
    }
    else
    {
        subsets[yRoot].Parent = xRoot;
        ++subsets[xRoot].Rank;
    }
}

public static (IList<Edge<int, TVertex>>, int) Kruskal<TVertex>(this Graph<TVertex, int> graph) where TVertex : IComparable
{
    var verticesCount = graph.Vertices.Count;
    var edges = graph.Edges.ToList();
    var result = new List<Edge<int, TVertex>>();

    var edgesCounter = 0;
    var verticesCounter = 0;
    var minCost = 0;

    edges.Sort();

    var subsets = new System.Collections.Generic.Dictionary<Vertex<TVertex, int>, Subset<TVertex, int>>();

    foreach (var vertex in graph.Vertices) // Массив множеств, вершины сами себе родители
    {
        subsets.Add(vertex, new Subset<TVertex, int>() {Parent = vertex, Rank = 0});
    }

    while (verticesCounter < verticesCount - 1)
    {
        var nextEdge = edges[edgesCounter++];

        var x = Find(subsets, nextEdge.InitialVertex);
        var y = Find(subsets, nextEdge.DestinationVertex);

        if (x != y)
        {
            result.Add(nextEdge);
            minCost += nextEdge.Weight;
            verticesCounter++;

            Union(subsets, x, y);
        }
    }

    return (result, minCost);
}

public static (IList<Edge<int, TVertex>>, int) Prima<TVertex>(this Graph<TVertex, int> graph) where TVertex : IComparable
{
    var minCost = 0;

    var notVisitedVertices = graph.Vertices.ToList();
    var visitedVertices = new List<Vertex<TVertex, int>>();

    var notVisitedEdges = graph.Edges.ToList();
    var visitedEdges = new List<Edge<int, TVertex>>();

    if (graph.Vertices.Count > 0)
    {
        // Выбираем первую вершину для просмотра
        var visitedVertex = notVisitedVertices[0];
        visitedVertices.Add(visitedVertex);
        notVisitedVertices.Remove(visitedVertex);

        while (notVisitedVertices.Count > 0)
        {
            var indexMinEdge = -1;

            for (var i = 0; i < notVisitedEdges.Count; i++) // Обходим не посещённые вершины
            {
                if (visitedVertices.IndexOf(notVisitedEdges[i].InitialVertex) != -1 && notVisitedVertices.IndexOf(notVisitedEdges[i].DestinationVertex) != -1 || 
                    visitedVertices.IndexOf(notVisitedEdges[i].DestinationVertex) != -1 && notVisitedVertices.IndexOf(notVisitedEdges[i].InitialVertex) != -1)
                {
                    if (indexMinEdge != -1)
                    {
                        if (notVisitedEdges[i].Weight < notVisitedEdges[indexMinEdge].Weight) indexMinEdge = i;
                    }
                    else
                    {
                        indexMinEdge = i;
                    }
                }
            }

            if (visitedVertices.IndexOf(notVisitedEdges[indexMinEdge].InitialVertex) != -1) // Проверка, что посещёна
            {
                visitedVertices.Add(notVisitedEdges[indexMinEdge].DestinationVertex);
                notVisitedVertices.Remove(notVisitedEdges[indexMinEdge].DestinationVertex);
            }
            else
            {
                visitedVertices.Add(notVisitedEdges[indexMinEdge].InitialVertex);
                notVisitedVertices.Remove(notVisitedEdges[indexMinEdge].InitialVertex);
            }

            visitedEdges.Add(notVisitedEdges[indexMinEdge]);
            minCost += notVisitedEdges[indexMinEdge].Weight;
            notVisitedEdges.RemoveAt(indexMinEdge);
        }
    }

    return (visitedEdges, minCost);
}