0

I'm testing merge sort with 100.000.000 numbers and it's hanging. I've done it with heap sort and time is 65s, i also do merge sort with 10,000,000 elements and it still done well. I don't know why it's hanging. Anyone have an idea?

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <fstream>

using namespace std;
void merge(int a[], int l, int m, int r)
{
    int i, j, k = l;
    int n1 = m - l + 1; // so phan tu cua mang 1
    int n2 = r - m;     // so phan tu cua mang 2
    int *L = new int[n1];
    int *R = new int[n2];

    for (i = 0; i < n1; i++)
        L[i] = a[l + i]; // sao chep cac phan tu cua mang can chia vao cac mang con
    for (j = 0; j < n2; j++)
        R[j] = a[m + j + 1];

    i = 0;
    j = 0;
    while (i < n1 && j < n2)
        if (L[i] < R[j])
            a[k++] = L[i++];
        else
            a[k++] = R[j++];
    while (i < n1)
        a[k++] = L[i++];
    while (j < n2)
        a[k++] = R[j++];
}
void mergeSort(int a[], int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;    // tim phan tu middle de chia
        mergeSort(a, l, m);     // chia
        mergeSort(a, m + 1, r); // chia
        merge(a, l, m, r);      // tron
    }
}
int main()
{

    int size;
    cout << "Nhap so phan tu cua mang sinh ngau nhien: ";
    cin >> size;
    int *arr = new int[size];
    srand(time(0));
    for (int i = 0; i < size; i++)
    {
        arr[i] = rand() % 2000000000;
    }

    mergeSort(arr, 0, size - 1);
    cout << "done!";
    return 0;
}

i have feeling it's because of int *arr= new int[size]

Anh Tuan
  • 1
  • 1
  • 8
    For one, because you're leaking memory like a sieve leaks rainwater in your `merge` function. – WhozCraig Nov 03 '22 at 15:05
  • OT: `arr[i]= rand() % 2000000000;` is your `int` this large? Does rand() even have that range? – drescherjm Nov 03 '22 at 15:06
  • `int *L = new int[n1];` --> `std::vector L(n1), R(n2);` . Also, if you want to see how to implement merge sort using modern C++ [see this link](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). – PaulMcKenzie Nov 03 '22 at 15:11
  • For sizes you should not use `int` but `std::size_t` and if you use `std::vector` you also might want to `use std::sort` (and see how much faster that is, and how much easier it is to reuse tested code) – Pepijn Kramer Nov 03 '22 at 15:12
  • 1
    If you want to understand why int won't fit your 2000000000, have a look here : https://en.cppreference.com/w/cpp/types/numeric_limits. And then check the value for int in your code. `int max_value = std::numeric_limits::max()` – Pepijn Kramer Nov 03 '22 at 15:16
  • @PepijnKramer - std::sort can be used with arrays, using pointers instead of iterators. – rcgldr Nov 03 '22 at 18:56
  • @rcgldr Fair enough, but they're not calls "C" style arrays for nothing. And switching from pre C++98 to C++11 long time ago I've noticed a fair drop in bugs/memory leaks in code that doesn't use them anymore. – Pepijn Kramer Nov 04 '22 at 06:22

1 Answers1

1

In merge, delete the two temp arrays:

    while (j < n2)              // existing code
        a[k++] = R[j++];
    delete[] R;                 // delete temp arrays
    delete[] L;

In main, delete arr:

    cout << "done!";            // existing code
    delete[] arr;               // delete arr

I'm not sure about rand(). I normally use this instead:

int rnd32()                     // visual studio rand is only 15 bits
{
static uint32_t r = 0;          // or = time(0)
    r = r*1664525 + 1013904223;
    return (int)r;
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61