using System;

using System.Collections.Generic;

using System.Threading;

using System.Threading.Tasks;

​

public static class MultiThreadedDoubleEndedSelectionSort

{

    private static object lockObj = new object();

​

    public static void Sort<T>(IList<T> arr) where T: IComparable<T>

    {

        int numThreads = Environment.ProcessorCount; // Number of available threads

​

        Task[] tasks = new Task[numThreads];

​

        for (int i = 0; i < numThreads; i++)

        {

            int startIndex = i * (arr.Count / numThreads);

            int endIndex = (i == numThreads - 1) ? arr.Count - 1 : ((i + 1) * (arr.Count / numThreads)) - 1;

​

            tasks[i] = Task.Run(() => SortSegment(arr, startIndex, endIndex));

        }

​

        Task.WaitAll(tasks);

​

        // After all threads finish, perform a final pass to ensure sorted order

        for (int i = 1; i < arr.Count; i++)

        {

            T key = arr[i];

            int j = i - 1;

​

            while (j >= 0 && arr[j].CompareTo(key) > 0)

            {

                arr[j + 1] = arr[j];

                j--;

            }

​

            arr[j + 1] = key;

        }

    }

​

    private static void SortSegment<T>(IList<T> arr, int left, int right) where T: IComparable<T>

    {

        while (left <= right)

        {

            int minIndex = left;

            int maxIndex = right;

​

            for (int i = left; i <= right; i++)

            {

                if (arr[i].CompareTo(arr[minIndex]) < 0)

                    minIndex = i;

                else if (arr[i].CompareTo(arr[maxIndex]) > 0)

                    maxIndex = i;

            }

​

            // Ensure that minIndex and maxIndex are not the same to avoid redundant swaps

            if (minIndex != maxIndex)

            {

                lock (lockObj)

                {

                    Swap(arr, left, minIndex);

​

                    // After the swap, the maxIndex might have changed position

                    if (maxIndex == left)

                        maxIndex = minIndex;

​

                    Swap(arr, right, maxIndex);

                }

            }

​

            left++;

            right--;

        }

    }

​

    private static void Swap<T>(IList<T> arr, int i, int j)

    {

        T temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

​

    public static void Main(string[] args)

    {

        IList<int> arr = new[] { 64, 25, 12, 22, 11, 1, 23, 13, 60 };

        Console.WriteLine("Original array:");

        PrintArray(arr);

​

        Sort(arr);

​

        Console.WriteLine("\nSorted array:");

        PrintArray(arr);

    }

​

    private static void PrintArray<T>(IEnumerable<T> arr)

    {

        foreach (var num in arr)

        {

            Console.Write(num + " ");

        }

        Console.WriteLine();

    }

}

​