public class SortAlgorithm
    {

        /*
         * Below for loop is alog for build heap
         * FOR (N/2-1) TO 0 <= Range of internal nodes
         *  HEAPIFIY(arr, i)
         */
        public void BuildMaxHeap(int[] arr)
        {
            int len = arr.Length;
            for (int i = (len / 2 - 1); i >= 0; i--)
                MaxHeapify(arr, i, len - 1);
        }

        public int[] HeapSort(int[] nums)
        {

            //nums = BuildMaxHeap(nums);

            int heapsize = nums.Length - 1;
            for (int i = heapsize; i > 0; i--)
            {
                //Extract Max OR min by swapping the root element with leaf element
                (nums[0], nums[i]) = (nums[i], nums[0]);
                heapsize--;
                MaxHeapify(nums, 0, heapsize);
            }

            return nums;

        }

        private void MaxHeapify(int[] array, int parentIndex, int indexLimit)
        {
            int leftChildIndex = 2 * parentIndex + 1;
            int rightChildIndex = 2 * parentIndex + 2;
            int maxIndex = parentIndex;
            if (leftChildIndex <= indexLimit && array[leftChildIndex] > array[parentIndex])
            {
                maxIndex = leftChildIndex;
            }

            if (rightChildIndex <= indexLimit && array[rightChildIndex] > array[maxIndex])
            {
                maxIndex = rightChildIndex;
            }

            if (maxIndex != parentIndex)
            {
                (array[parentIndex], array[maxIndex]) = (array[maxIndex], array[parentIndex]);
                MaxHeapify(array, maxIndex, indexLimit);
            }
        }

        public int[] MergeSort(int[] nums)
        {
            int size = nums.Length;
            if (size < 2)
                return nums;
            int mid = size / 2;
            int[] leftHalf = new int[mid];
            int[] rightHalf = new int[size - mid];

            for (int i = 0; i < mid; i++)
            {
                leftHalf[i] = nums[i];
            }
            for (int i = mid; i < size; i++)
            {
                rightHalf[i-mid] = nums[i];
            }
            MergeSort(leftHalf);
            MergeSort(rightHalf);
            Merge(nums, leftHalf, rightHalf, mid, size - mid);
            return nums;
        }

        private void Merge(int[] arr, int[] leftHalf, int[] rightHalf, int leftBoundary, int rightBoundary)
        {
            int leftIndex = 0;
            int rightIndex = 0;
            int arrayIndex = 0;

            while (leftIndex < leftBoundary && rightIndex < rightBoundary)
            {
                if (leftHalf[leftIndex] < rightHalf[rightIndex])
                {
                    arr[arrayIndex] = leftHalf[leftIndex];
                    leftIndex++;
                }
                else
                {
                    arr[arrayIndex] = rightHalf[rightIndex];
                    rightIndex++;
                }

                arrayIndex++;
            }
            while (leftIndex < leftBoundary)
            {
                arr[arrayIndex] = leftHalf[leftIndex];
                arrayIndex++;
                leftIndex++;
            }
            while (rightIndex < rightBoundary)
            {
                arr[arrayIndex] = rightHalf[rightIndex];
                arrayIndex++;
                rightIndex++;
            }
        }
    }