Insertion sort crashing at certain array sizes but not others?

*By size, I mean number of elements

My insertion sort program is crashing at some array sizes but not others.* If I feed an unordered array of size 80+ or an ordered array of 100+ or a reversed ordered array of 100+, it will crash. It won't crash for any array below that size, I've tested.

The error is malloc: Incorrect checksum fo freed object 0x7fed6cc02bb0: probably modified after being freed.

I've checked for allocating and deleting memory... no issues as far as I can tell. I'm having a hard time understanding why it's crashing at specific numbers for different array types.

void sort(int* const array, int size) const{
    int key = 1;

    for (int i = 0; i < size; i++){
        if(array[key] < array[i]){
            traverse(array, key);
        }
        key++;
    }
    std::cout << "here" << std::endl;
}

void traverse(int* const array, int key) const{
    int i = key - 1;
    while(array[key] < array[i]){
        std::cout << "key = ";
        std::cout << key << std::endl;

        std::cout << "i = ";
        std::cout << i << std::endl;

        if(key == 0){
            return;
        }
        else if(array[key] < array[i]){
            swap(array[i], array[key]);
        }
        key--;
        i--;
    }
}

void swap(int &a, int &b) const{
    int hold = a;
    a = b;
    b = hold;
}
void unordered(int size){
  time_t t;
  srand((unsigned) time(&t));

  int* array = new int[size];
  for(int i = 0; i < size; i++)
    array[i] = (rand() % size) + 1;

  sort(array, size);

  bool b = isSorted(array, size);
  assert(b == true);
  delete [] array;
}

void ordered(int size){
  int* array = new int[size];
  for(int i = 0; i < size; i++)
    array[i] = i;

  sort(array, size);

  bool b = isSorted(array, size);
  assert(b == true);
  delete [] array;
}

int main(){
  unordered(5);
  unordered(30);
  unordered(40);
  unordered(50);
  unordered(60);
  unordered(80);
}

In the above code, I believe it's crashing at unordered(80) in sort() right after leaving the for loop since the last thing the program prints out is:

key = 2
i = 1
here