using System;
using System.Threading;
using System.Threading.Tasks;

namespace SortVisualizer;

public class MergeSort : ISortAlgorithm
{
    public string Name => "Merge Sort";
    public MergeSort() { }
    public async Task Sort(int[] array, Action refresh, int delay, Action<int> playSound, CancellationToken token)
    {
        await MergeSortRecursive(array, 0, array.Length - 1, refresh, delay, playSound, token);
    }

    private async Task MergeSortRecursive(int[] array, int left, int right, Action refresh, int delay, Action<int> playSound, CancellationToken token)
    {
        token.ThrowIfCancellationRequested();

        if (left >= right) return;

        int mid = (left + right) / 2;
        await MergeSortRecursive(array, left, mid, refresh, delay, playSound, token);
        await MergeSortRecursive(array, mid + 1, right, refresh, delay, playSound, token);
        await Merge(array, left, mid, right, refresh, delay, playSound, token);
    }

    private async Task Merge(int[] array, int left, int mid, int right, Action refresh, int delay, Action<int> playSound, CancellationToken token)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        Array.Copy(array, left, L, 0, n1);
        Array.Copy(array, mid + 1, R, 0, n2);

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2)
        {
            token.ThrowIfCancellationRequested();

            if (L[i] <= R[j])
            {
                array[k] = L[i];
                playSound?.Invoke(L[i]);
                i++;
            }
            else
            {
                array[k] = R[j];
                playSound?.Invoke(R[j]);
                j++;
            }

            refresh?.Invoke();
            await Task.Delay(delay, token);
            k++;
        }

        while (i < n1)
        {
            token.ThrowIfCancellationRequested();
            array[k] = L[i];
            playSound?.Invoke(L[i]);
            i++; k++;
            refresh?.Invoke();
            await Task.Delay(delay, token);
        }

        while (j < n2)
        {
            token.ThrowIfCancellationRequested();
            array[k] = R[j];
            playSound?.Invoke(R[j]);
            j++; k++;
            refresh?.Invoke();
            await Task.Delay(delay, token);
        }
    }
}
