Return to Question

 

---

Edit:

I made merge_sort and merge take a T tmp[]. And I made a "wrapper" function around merge_sort like this:

template<typename T>
void merge_sort(T* sequence, int size)
{
    T* tmp = new T[size];
    _merge_sort(sequence, tmp, size);
    delete[] tmp;
}

Now new is only called once. The "old" merge_sort is renamed to _merge_sort.

I'm a first year computer engineering student who's learning about algorithms and data structures. I've implemented a parallel merge sort algorithm in C++ and would like constructive criticism. This was done in Visual Studio on Windows.

Some thoughts:

• portability isn't a concern I have atm.
• merge_sort isn't using tail recursion, which I would like it to do

---

**function merge:** ```C++ template void merge(T sequence[], int size) { T* sorted = new T[size]; int middle = size / 2;

int index_left = 0;
int index_right = middle;
int index_sequence = 0;

while (index_left < middle && index_right < size)
{
    if (sequence[index_left] < sequence[index_right])
        sorted[index_sequence++] = sequence[index_left++];
    else
        sorted[index_sequence++] = sequence[index_right++];
}

while (index_left < middle)
    sorted[index_sequence++] = sequence[index_left++];

while (index_right < size)
    sorted[index_sequence++] = sequence[index_right++];

for (int i = 0; i < size; i++)
    sequence[i] = sorted[i];

delete[] sorted;

}

<br>
**function merge_sort:**
```C++
template<typename T, int min_size_to_thread = 10000>
void merge_sort(T sequence[], int size)
{
    if (size > 1)
    {
        int middle = size / 2;
        if (size > min_size_to_thread)
        {
            std::thread left(merge_sort<T, min_size_to_thread>, &sequence[0], middle);
            std::thread right(merge_sort<T, min_size_to_thread>, &sequence[middle], size - middle);
            left.join();
            right.join();
        }
        else
        {
            merge_sort<T, min_size_to_thread>(&sequence[0], middle);
            merge_sort<T, min_size_to_thread>(&sequence[middle], size - middle);
        }
        merge<T>(sequence, size);
    }
}

---

For those who are interested: I Did some performance testing on a i5-2530M 2.50Ghz (2 cores).
The sequence to merge sort is int[100000]

I'm a first year computer engineering student who's learning about algorithms and data structures. I've implemented a parallel merge sort algorithm in C++ and would like constructive criticism. This was done in Visual Studio on Windows.

Some thoughts:

• portability isn't a concern I have atm.
• merge_sort isn't using tail recursion, which I would like it to do

---

**includes:** `#include `
**function merge:** ```C++ template void merge(T sequence[], int size) { T* sorted = new T[size]; int middle = size / 2;

int index_left = 0;
int index_right = middle;
int index_sequence = 0;

while (index_left < middle && index_right < size)
{
    if (sequence[index_left] < sequence[index_right])
        sorted[index_sequence++] = sequence[index_left++];
    else
        sorted[index_sequence++] = sequence[index_right++];
}

while (index_left < middle)
    sorted[index_sequence++] = sequence[index_left++];

while (index_right < size)
    sorted[index_sequence++] = sequence[index_right++];

for (int i = 0; i < size; i++)
    sequence[i] = sorted[i];

delete[] sorted;

}

<br>
**function merge_sort:**
```C++
template<typename T, int min_size_to_thread = 10000>
void merge_sort(T sequence[], int size)
{
    if (size > 1)
    {
        int middle = size / 2;
        if (size > min_size_to_thread)
        {
            std::thread left(merge_sort<T, min_size_to_thread>, &sequence[0], middle);
            std::thread right(merge_sort<T, min_size_to_thread>, &sequence[middle], size - middle);
            left.join();
            right.join();
        }
        else
        {
            merge_sort<T, min_size_to_thread>(&sequence[0], middle);
            merge_sort<T, min_size_to_thread>(&sequence[middle], size - middle);
        }
        merge<T>(sequence, size);
    }
}

---

For those who are interested: I Did some performance testing on a i5-2530M 2.50Ghz (2 cores).
The sequence to merge sort is int[100000]

I'm a first year computer engineering student who's learning about algorithms and data structures. I've implemented a parallel merge sort algorithm in C++ and would like constructive criticism. This was done in Visual Studio on Windows.

Some thoughts:

• portability isn't a concern I have atm.
• merge_sort isn't using tail recursion, which I would like it to do

---

**function merge:** ```C++ template void merge(T sequence[], int size) { T* sorted = new T[size]; int middle = size / 2;

int index_left = 0;
int index_right = middle;
int index_sequence = 0;

while (index_left < middle && index_right < size)
{
    if (sequence[index_left] < sequence[index_right])
        sorted[index_sequence++] = sequence[index_left++];
    else
        sorted[index_sequence++] = sequence[index_right++];
}

while (index_left < middle)
    sorted[index_sequence++] = sequence[index_left++];

while (index_right < size)
    sorted[index_sequence++] = sequence[index_right++];

for (int i = 0; i < size; i++)
    sequence[i] = sorted[i];

delete[] sorted;

}

<br>
**function merge_sort:**
```C++
template<typename T, int min_size_to_thread = 10000>
void merge_sort(T sequence[], int size)
{
    if (size > 1)
    {
        int middle = size / 2;
        if (size > min_size_to_thread)
        {
            std::thread left(merge_sort<T, min_size_to_thread>, &sequence[0], middle);
            std::thread right(merge_sort<T, min_size_to_thread>, &sequence[middle], size - middle);
            left.join();
            right.join();
        }
        else
        {
            merge_sort<T, min_size_to_thread>(&sequence[0], middle);
            merge_sort<T, min_size_to_thread>(&sequence[middle], size - middle);
        }
        merge<T>(sequence, size);
    }
}

 

For those who are interested: I Did some performance testing on a i5-2530M 2.50Ghz (2 cores).
The sequence to merge sort is int[100000]

I'm a first year computer engineering student who's learning about algorithms and data structures. I've implemented a parallel merge sort algorithm in C++ and would like constructive criticism. This was done in Visual Studio on Windows.

Some thoughts:

• portability isn't a concern I have atm.
• merge_sort isn't using tail recursion, which I would like it to do

---

**function merge:** ```C++ template void merge(T sequence[], int size) { T* sorted = new T[size]; int middle = size / 2;

int index_left = 0;
int index_right = middle;
int index_sequence = 0;

while (index_left < middle && index_right < size)
{
    if (sequence[index_left] < sequence[index_right])
        sorted[index_sequence++] = sequence[index_left++];
    else
        sorted[index_sequence++] = sequence[index_right++];
}

while (index_left < middle)
    sorted[index_sequence++] = sequence[index_left++];

while (index_right < size)
    sorted[index_sequence++] = sequence[index_right++];

for (int i = 0; i < size; i++)
    sequence[i] = sorted[i];

delete[] sorted;

}

<br>
**function merge_sort:**
```C++
template<typename T, int min_size_to_thread = 10000>
void merge_sort(T sequence[], int size)
{
    if (size > 1)
    {
        int middle = size / 2;
        if (size > min_size_to_thread)
        {
            std::thread left(merge_sort<T, min_size_to_thread>, &sequence[0], middle);
            std::thread right(merge_sort<T, min_size_to_thread>, &sequence[middle], size - middle);
            left.join();
            right.join();
        }
        else
        {
            merge_sort<T, min_size_to_thread>(&sequence[0], middle);
            merge_sort<T, min_size_to_thread>(&sequence[middle], size - middle);
        }
        merge<T>(sequence, size);
    }
}

 

---

For those who are interested: I Did some performance testing on a i5-2530M 2.50Ghz (2 cores).
The sequence to merge sort is int[100000]