Visual Studio 2010 — Ошибка при выделении памяти в переполнении стека

Ваша проблема коррупции заключается в следующем:

k = low;

Вы используете k как индекс в ваш временный массив. Должно начинаться с 0, а не low Измените это на:

k = 0;

Что касается остальной части вашего алгоритма, у вас есть явная утечка памяти. Вы не удаляете ваш временный массив. Кроме того, алгоритм сортировки слиянием в C и C ++ значительно проще, чем в большинстве языков, именно благодаря своей нативной способности с арифметикой указателей.

Например:

template<typename T>
void merge(T* ar, size_t mid, size_t len)
{
T *merged = new T[len]; // note. normally i would use a smart pointer

size_t i=0, j=mid, k=0;
while (i<mid && j<len)
{
if (ar[i] < ar[j])
merged[k++] = ar[i++];
else
merged[k++] = ar[j++];
}

while (i < mid)
merged[k++] = ar[i++];
while (j < len)
merged[k++] = ar[j++];

std::copy(merged, merged+k, ar);
delete [] merged;
}

template<typename T>
void mergesort(T* ar, size_t len)
{
if (len<2)
return;

mergesort(ar, len/2);
mergesort(ar+len/2, len-len/2);
merge(ar, len/2, len);
}

Используя вышеупомянутое. следующее демонстрирует, как это называется:

int main()
{
std::random_device rd;
std::default_random_engine rng(rd());
std::uniform_int_distribution<> dist(1,99);

std::vector<int> data;
data.reserve(25);
std::generate_n(std::back_inserter(data), data.capacity(),
[&](){ return dist(rng);});

for (auto x : data)
std::cout << x << ' ';
std::cout << '\n';

mergesort(data.data(), data.size());

for (auto x : data)
std::cout << x << ' ';
std::cout << '\n';

return 0;
}

Выход (очевидно, меняется)

55 39 40 87 49 1 94 8 20 47 42 23 93 99 81 52 17 66 3 6 74 5 49 13 67
1 3 5 6 8 13 17 20 23 39 40 42 47 49 49 52 55 66 67 74 81 87 93 94 99

Все это говорит, если только это не для научных кругов, вы без ума не просто использовать std::sort

Альтернативное Распределение

Восходящий дизайн хорошо работает в разных случаях, но система распределения памяти, которую он использует, ужасна для больших наборов. Общее необходимое временное пространство никогда не будет больше N предметы для NКонтейнер -item, так что вы можете заранее выделить его с фронтальным загрузчиком для фактической сортировки слиянием, которая затем вместе с алгоритмом слияния предоставляет временное пространство для использования, а не выделяет свое собственное. Единственная сложность — знать, где в хранилище tmp безопасно использовать пространство. Но вы уже знаете это. Те же смещения, которые вы используете для сортируемой последовательности, также могут быть использованы для правильного сопоставления местоположений временного пространства:

template<typename T>
void merge(T* ar, size_t mid, size_t len, T* tmp)
{
size_t i=0, j=mid, k=0;
while (i<mid && j<len)
{
if (ar[i] < ar[j])
tmp[k++] = ar[i++];
else
tmp[k++] = ar[j++];
}

while (i < mid)
tmp[k++] = ar[i++];
while (j < len)
tmp[k++] = ar[j++];

std::copy(tmp, tmp+k, ar);
}template<typename T>
void mergesort_int(T* ar, size_t len, T* tmp)
{
if (len < 2)
return;

mergesort_int(ar, len/2, tmp);
mergesort_int(ar+len/2, len-len/2, tmp+len/2);
merge(ar, len/2, len, tmp);
}

template<typename T>
void mergesort(T* ar, size_t len)
{
if (len<2)
return;

std::vector<T> tmp(len)
mergesort_int(ar, len, &tmp[0]);
}

Используя то же самое main() Исходя из предыдущего примера, результат аналогичен:

24 9 26 93 35 75 99 95 49 58 32 37 30 88 55 13 76 23 99 90 50 66 38 8 3
3 8 9 13 23 24 26 30 32 35 37 38 49 50 55 58 66 75 76 88 90 93 95 99 99

Помните, что теперь требуется один не замужем распределение N items (в нашем случае мы используем вектор для автоматического управления памятью), который затем используется в алгоритме. Вы найдете это значительно быстрее, особенно для большой наборы данных.