вставить элемент в отсортированный массив

Question

Я работаю над домашней работой, которая требует:

Create a dynamic array of 1,000,000 ints. Each int is randomly generated between -50,000 and 50,000. As each int is generated, it is inserted into the array in sorted order. Do NOT fill the array and then sort it.

Я вроде как понял, но все еще есть две проблемы с этим.

~ IDE показывает Thread 1: EXC_BAD_ACCESS, когда я установил размер 1000000 или 100000.

Меня удивило, потому что 100 000 целых занимают меньше половины мегабайта, верно?

~ 10000 целых занимает 1м25 с, а 20 000 - 12 м.

Неужели это так? нормально, что время увеличивается так сильно, когда я удваиваю размер? мой алгоритм O (n).

Я не взял ни одного класса DS, и мне не разрешено использовать вектор. На самом деле не знаю, что делать, кроме смещения элементов при вставке элемента в массив.

Любая помощь будет по достоинству оценена.

const int SIZE = 10000;

int randBetween(const int &, const int &);
int findIndex(const int, array<int, SIZE>, int begin, int end);

int main(int argc, const char * argv[]) {
    srand(time(0));
    int randomNum = 0;
    int index = 0;
    int numOfElements = 0;  // number of random number generated
    int count = 0;          // number of elments get printed
    int hours = 0;
    int minutes = 0;
    int seconds  = 0;
    const int min = -50000;
    const int max = 50000;

    auto start = std::chrono::high_resolution_clock::now();
    array<int, SIZE> intArray;
    intArray.at(0) = randBetween(min, max);
    numOfElements++;

    cout << "in progress..." << endl;

    for(auto it = intArray.begin() + 1; it != intArray.end(); it++){
        numOfElements++;
        randomNum = randBetween(min, max);
        index = findIndex(randomNum, intArray, 0, numOfElements - 1);
        // shift all elements after index of randomNum by 1
        for (int i = (numOfElements - 1); i > index ; i--){
            intArray.at(i) = intArray.at(i - 1);
        }
        // insert randomNum into array at index found
        intArray.at(index) = randomNum;
    }
    cout << endl << "begin: " << endl;
    for (auto it = intArray.begin(); it != intArray.end(); it++) {
        count++;
        cout << right << setw(6) << *it << " ";
        if((count) % 10 == 0) cout << endl;
    }
    cout << "end..." <<endl;

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    seconds = static_cast<int>(elapsed.count()) % 60;
    minutes = elapsed.count() / 60;
    hours = minutes / 60;
    cout << fixed << hours << " Hours, " << minutes << " Minutes, " << seconds << " Seconds elapsed.";

    return 0;
}
int randBetween(const int &min, const int &max){
    return (rand()% (max - min + 1) + min);
}

int findIndex(const int num, array<int, SIZE> intArray, int begin, int end){
    int index = 0;
    while (begin <= end) {
        index = (begin + end )/ 2;
        if (num == intArray.at(index)) {
            break;
        }else if (num < intArray.at(index)){
            if (index == begin){
                break;
            }else if (num >= intArray.at(index - 1)) {
                break;
            }
            end = index;
            findIndex(num, intArray, begin, end);
        }else if (num > intArray.at(index)){
            if ((index + 1 )== end){
                index++;
                break;
            }else if (num <= intArray.at(index)) {
                index++;
                break;
            }
            begin = index;
            findIndex(num, intArray, begin, end);
        }
    }
    return index;
}