There was a problem in the merge sort program. The initial array filled with random numbers is “divided” into two sub-arrays, each of which is sorted separately (if there are more than 5000 elements in the original array, then sorting is used by selection, if less - gnome is sorting) and then they merge into the resulting array. The problem is that if you set the array length to more than 128,000, the program crashes.

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int main() { const int length = 128000; int arr1[length]; int i; for (i = 0; i<length; i++) { arr1[i] = (rand() % 99)+1; cout << arr1[i] << " "; } int counter1, counter2, counter3; //array's counters counter1 = 0; //не больше (length-2)/2 counter2 = length / 2; //не больше length-1 counter3 = 0; //не больше length-1 if (length>5000) { int j, k; int number;//the number of the maximum element int maximum;//the maximum element for (j = counter1; j <= (length - 2) / 2; j++) { maximum = arr1[j]; number = j; for (k = j + 1; k <= (length - 2) / 2 - 1; k++) { if (maximum>arr1[k]) { maximum = arr1[k]; number = k; } } swap(arr1[j], arr1[number]); } for (j = counter2; j <= length - 2; j++) { maximum = arr1[j]; number = j; for (k = j + 1; k <= length - 1; k++) { if (maximum>arr1[k]) { maximum = arr1[k]; number = k; } } swap(arr1[j], arr1[number]); } } else { int j = counter1; while (j<(length - 2) / 2 + 1) { if (j == 0 || arr1[j - 1] <= arr1[j]) j++; else { swap(arr1[j], arr1[j - 1]); j--; } } int k = counter2; while (k<length) { if (k == 0 || arr1[k - 1] <= arr1[k]) k++; else { swap(arr1[k], arr1[k - 1]); k--; } } } int arr2[length]; int l; while (counter3 != length) { if (arr1[counter1] <= arr1[counter2]) { arr2[counter3] = arr1[counter1]; counter1++; if (counter1 == (length - 2) / 2 + 1) { counter3++; for (l = counter2; l <= length - 1; l++) { arr2[counter3] = arr1[l]; counter3++; } break; } } else { arr2[counter3] = arr1[counter2]; counter2++; if (counter2 == length) { counter3++; for (l = counter1; l <= (length - 2) / 2; l++) { arr2[counter3] = arr1[l]; counter3++; } break; } } counter3++; } int s; cout << "\n"; for (s = 0; s <= length - 1; s++) cout<< arr2[s]; return 0;

}

  • Why is the tag [C] here? - AnT

1 answer 1

The short answer is 128,000 * 4 = this is half a megabyte.

Your array is allocated on the stack, and the stack in most modern systems is usually no more than 1 megabyte per stream. Want more - use std::vector<int> .

It is very likely that replacing the string

 int arr1[length];

on

 std::vector<int> arr1(length);

and adding #include <vector> to the very top will work.

But you can of course allocate memory through malloc / new. But this is not fashionable, and requires substantial alteration of the program.