C ++: hybrid and plug-in hybrid

I am trying to create a hybrid of merge and insert sort in C ++. However, when I enter these numbers into the exact ordering algorithm, 9,1,1,4,4,0,3,8,5,7,9,5,9,1,3,3,1,5,7,0,7,2

(22 numbers by the way), I get:, 1,1,0,1,1,0,2,3,3,3,4,4,5,5,5,7,7,7,8,9,9,9

which is clearly not sorted correctly.

If you're wondering if any of my individual algorithms are wrong, the answer is no. I tested my merge and insert sort algorithms individually using the same numbers in the same order and each produced a properly sorted array of numbers.

So the algorithm was probably wrong somewhere in the extra code that is needed to glue the two algorithms together. (I also changed the insertion sort code slightly to make it more efficient, but that's not a problem either, in case you're wondering. Both tests on the algorithm before and after I changed it gave the same result: wrong result. )

Here's my code if you want to see it:

#include <iostream>

void sort (int *array, int low, int mid, int high) {
    //Insertion sort
    for (int i = mid; i < high; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (array[i] < array [j]) {
                int holder = array[j];
                array[j] = array[i];
                array[i] = holder;
                i--;
            }
        }
    }
}
void merge (int *array, int *sub, int low, int mid, int high) {
    //Merge part of mergesort
    int a = low;
    int b = low;
    int c = mid;

    while ((a < mid) && (c < high)) {
        if (array[a] <= array[c]) {
            sub[b] = array[a];
            a++;
        } else {
            sub[b] = array[c];
            c++;
        }
        b++;
    }
    while (a == mid && c < high) {
        sub[b] = array[c];
        c++;
        b++;
    }
    while (c == high && a < mid) {
        sub[b] = array[a];
        a++;
        b++;
    }
    for (int d = low; d < high; d++) {
        array[d] = sub[d];
    }
}
void split (int *array, int *sub, int low, int high) {
    //Split part of mergesort
    if (low < high - 1) {
        int mid = (low + high) / 2;
        split(array, sub, low, mid);
        split(array, sub, mid, high);
        if ((high - low) > 10){
            merge(array, sub, low, mid, high);
        } else {
            sort(array, low, mid, high);
        }

    }
}

int main()
{
    std::cout << "This is a program that sorts integers.\n";
    std::cout << "How many numbers would you like to sort?\n";
    int num;
    std::cin >> num;
    if (num < 0) {
        std::cout << "Invalid amount of numbers.\n";
        return 0;
    } else if (num == 0) {
        std::cout << "No numbers to sort.\n";
        return 0;
    } else if (num == 1) {
        std::cout << "Please type in the number.\n";
        std::cin >> num;
        std::cout << "Your sorted number is: " << num << ".\n";
        return 0;
    }
    int * array = new int [num];
    int * sub = new int [num];
    std::cout << "Please type in the numbers.\n";
    for (int i = 0; i < num; i++) {
        std::cin >> array[i];
    }
    split(array, sub, 0, num);
    std::cout << "Your sorted numbers are: ";
    for (int i = 0; i < num; i++) {
        std::cout << array[i];
        if (i != num - 1) {
            std::cout << ", ";
        } else {
            std::cout << ".\n";
        }
    }
    delete[] array;
    delete[] sub;

    return 0;

}

      

        
        
        
      

    

Any help on this would be greatly appreciated. Thanks in advance.