The function sorts an array of instances of the contact structure by the sname field; for fairly large arrays, there is a problem with stack overflow due to recursion in 5-6 lines. How can this sort be implemented without recursion?

 void MergeSort(contact* buf, int first, int last) { if (first >= last - 1) return; int mid = (first + last) / 2; MergeSort(buf, first, mid); MergeSort(buf, mid, last); contact * mas = new contact[last - first]; for (int i = first; i < last; ++i) mas[i - first] = buf[i]; int l = 0, r = mid - first; for (int i = first; i < last; ++i) { if (l == mid - first) buf[i] = mas[r++]; else if (r == last - first) buf[i] = mas[l++]; else if (strcmp(mas[l].sname, mas[r].sname) < 0) buf[i] = mas[l++]; else buf[i] = mas[r++]; } delete[] mas; }
  • one
    Just interesting - a large array - how much? Just getting a stack overflow at the log n recursion depth - you have to try it ... - Harry

1 answer 1

Stack overflow is possible here only with some special compilation options. for example, when compiling in debug mode. The answer to your question is here , but you hardly need exactly that. Don't forget to fix the middle item search error. Instead

 int mid = (first + last) / 2;

better to write

 int mid = first + (last-first) / 2;

because, I suspect, the indices are non-negative - and the first option will overflow if the array is really, as you said, very large.

  • if it is compiled in 32-bit mode, and we sort int = 4 байта then the maximum dimension is ~ 1 billion, if it is less than 2 billion, the limit value. And if 64 bits, then int = 8 байт and overflow in the near future will not succeed. - pavel