Binary Insertion Sort работает быстрее чем Merge Sort

я написал два алгоритма сортировки, первый из них - сортировка вставками, поиск позиции, куда нужно вставить элемент, выполняется через двоичный поиск:

static void BinaryInsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        /*// search for the position //*/
        int mid = 0;
        int low = 0;
        int high = i - 1;
        while (low < high)
        {
            if (arr[i] >= arr[mid])
                low = mid + 1;
            else if (arr[i] <= arr[mid])
                high = mid;
            mid = low + (high - low) / 2;
        }
        /*//*/ 
        if (arr[i] > arr[mid])
            mid = mid + 1;
        int result = arr[i];
        for (int k = i; k > mid; k--)
        {
            arr[k] = arr[k - 1];
        }
        arr[mid] = result;
    }
}

Второй из них - Сортировка Слиянием / Соединением. В теории она должна быть намного быстрее чем сортировка вставками:

static void Merge(int[] array, int first, int last, int end)
{
    while (first <= last && last < end)
    {
        if (array[last + 1] <= array[first])
        {
            int element = array[last + 1];
            for (int i = last + 1; i > first; i--)
                array[i] = array[i - 1];
            array[first] = element;
            last++;
        }
        first++;
    }
}
static void MergeSort(int[] array, int start, int end)
{
    if (end - start > 1)
    {
        int mid = start + (end - start) / 2;
        MergeSort(array, mid + 1, end);
        MergeSort(array, start, mid);
        Merge(array, start, mid, end);
    }
    else
    {
        Merge(array, start, start, end);
    }
}
static void MergeSort(int[] array)
{
    MergeSort(array, 0, array.Length - 1);
}

А теперь внимание: сортировка 250000 элементов. Казалось бы, при таком большом количестве элементов сортировка слияниями должна работать намного быстрее, ведь временная сложность сортировки слияниями O(n*log(n)), что дает в этом случае 448,289,2 итераций по сравнению с 625,000,000,00, которые в теории должна дать функция сортировки вставками.

Но при этом всем, даже когда разница такая большая, Merge Sort работает либо медленнее, либо же лучше, но совсем на чуть-чуть, чем Binary Insertion Sort.

Я хотел бы узнать, может быть я что-то не так написал, неэффективно воплотил алгоритм? У меня есть предположение, что это из-за рекурсии. Но неужели она настолько медленее, чем итеративный метод?

Вот результаты тестов: