Ускорение сортировки - C#

Формулировка задачи:

Для решения этой задачи использую быструю сортировку, но при проверке массива из 10^6 элементов время выполнения больше ограничения в 2 секунды. Мб тут нужно использовать другую сортировку? Задача:

Дан массив, элементами которого являются целые числа. Требуется отсортировать его по неубыванию. Входные данные Первая строка содержит целое число N (1 ≤ N ≤ 10^6) — количество элементов массива. Вторая строка содержит N целых чисел ai ( - 2^31 ≤ ai < 2^31) — элементы массива. Выходные данные Выведите, разделяя пробелами, N целых чисел — элементы массива в порядке неубывания.

Код стандартный:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace B
{
    class Program
    {
        static void quickSort(int[] a, int l, int r)
        {
            int temp;
            int x = a[l + (r-l)/2];
            int i = l;
            int j = r;
            while (i <= j)
            {
                while(a[i] < x) i++;
                while (a[j] > x) j--;
                if (i <= j)
                {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    i++;
                    j--;
                }
            }
            if (i < r)
                quickSort(a, i, r);
            if (l < j)
                quickSort(a, l, j);
        }
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int[] arr = new int[n];
            string str = Console.ReadLine();
            string[] mas = str.Split(' ');
            for (int i = 0; i < n; i++)
            {
                arr[i] = int.Parse(mas[i]);
            }
            quickSort(arr, 0, n - 1);
            for (int i = 0; i < n; i++)
            {
                Console.Write(arr[i]);
                Console.Write(' ');
            }
        }
    }
}

Решение задачи: «Ускорение сортировки»

textual
                            Листинг программы 
                        

                                        for (int i = 0; i < n; i++)
            {
                Console.Write(arr[i]);
                Console.Write(' ');
            }
                        