C++: mergesort and insertion sort hybrid

Question

I've been trying to create a mergesort and insertion sort hybrid in c++. However, whenever I type these numbers into the algorithm with the exact order, 9,1,1,4,4,0,3,8,5,7,9,5,9,1,3,3,1,5,7,0,7,2(that's 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 obviously isn't sorted correctly.

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

So the algorithm probably went wrong somewhere in additional code that was needed in order to glue the two algorithms together. (I also changed the insertion sort code a bit to make it more efficient, but that isn't the problem either, in case you were wondering. Both tests on the algorithm before and after I changed it produced the same result: the 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.

Answer 1

There are two issues in your sort() routine - you're only sorting from mid to high (instead of low to high), leaving things half-unsorted. Once that's fixed, you need to stop j when it moves below low, not 0, since we're not always working from the start of the array.

Finally, mid is no longer needed in that function.

void sort (int *array, int low, int high) {
    //Insertion sort
    for (int i = low; i < high; i++) {
        for (int j = i - 1; j >= low; j--) {
            if (array[i] < array [j]) {
                int holder = array[j];
                array[j] = array[i];
                array[i] = holder;
                i--;
            }
        }
    }
}

And later, in split(), adjust the call:

sort(array, low, high);

Working example: https://ideone.com/B1UtSK