insert element into array sorted order

Question

I am working on homework which requires:

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.

I kind of figure it out but still have two problems with it.

~ IDE shows Thread 1: EXC_BAD_ACCESS when I set the size to 1,000,000 or 100,000.

It surprised me because 100,000 integers only take less than half meg of space, right?

~ 10,000 integers take 1m25s to compile, and 20,000 take 12m.

Is it normal that time increases this much when I double the size? is my algorithm O(n).

I haven't taken any DS class, and not allowed to use vector. Really don't know what to do besides shifting elements when inserting an element into array.

Any help will be really appreciated.

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;
}