Проблема с InsertionSort при сортировке 1000000 элементов массива

На определенном этапе программа просто прекращает работу.

using System;
using System.Diagnostics;
 
class InsertionSort {
 
    // Функция сортировки массива с использованием сортировки вставкой
    void sort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
 
            // Переместить элементы arr [0..i-1], которые больше, чем key, на одну позицию впереди их текущей позиции
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
 
    // Функция для печати массива размера n
    static void printArray(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
 
        Console.Write("\n");
    }
 
    // Запуск кода
    public static void Main()
    {
        Stopwatch sw = new Stopwatch();
        int[] arr = new int[150000];
        Random rd = new Random();
        for(int i=0; i<arr.Length; ++i){
            arr[i] = rd.Next(10,150001);
        }
        sw.Start();
        Console.WriteLine("Given Array");
        printArray(arr);
        InsertionSort ob = new InsertionSort();
        //ob.sort(arr, 0, arr.Length - 1);
        ob.sort(arr);
        Console.WriteLine("\nSorted array");
        printArray(arr);
        sw.Stop();
        Console.WriteLine("Sorted time= {0} ", (sw.ElapsedMilliseconds / 1000.0).ToString());
        sw.Reset();

    }
}