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

Question

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

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();

}

}