Ttykuu

OP Amp not amplifying audio signal

What's the meaning of "Sollensaussagen"?

Send out email when Apex Queueable fails and test it

Do creatures with a speed 0ft., fly 30ft. (hover) ever touch the ground?

Could the museum Saturn V's be refitted for one more flight?

What reasons are there for a Capitalist to oppose a 100% inheritance tax?

How to compactly explain secondary and tertiary characters without resorting to stereotypes?

Pact of Blade Warlock with Dancing Blade

Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?

How exploitable/balanced is this homebrew spell: Spell Permanency?

Bullying boss launched a smear campaign and made me unemployable

My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?

How to show a landlord what we have in savings?

Why was the shrink from 8″ made only to 5.25″ and not smaller (4″ or less)

Knowledge-based authentication using Domain-driven Design in C#

Why are UK visa biometrics appointments suspended at USCIS Application Support Centers?

Processor speed limited at 0.4 Ghz

How do conventional missiles fly?

Mathematica command that allows it to read my intentions

What is the most common color to indicate the input-field is disabled?

Machine learning testing data

Getting extremely large arrows with tikzcd

What does the same-ish mean?

How to stretch the corners of this image so that it looks like a perfect rectangle?

C++ parallel merge sort

Parallel Merge SortMerge Sort in C++Merge Sort algorithmParallel Merge Sort in ScalaRun-aware merge sortSlow merge sortParallel merge sort in JavaMultithreaded bottom up merge sortC++ Merge Sort ImplementationC++: Merge Sort Implementation

2

$begingroup$

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:

template<typename T>
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;

function merge_sort:

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]

c++ beginner multithreading sorting mergesort

share|improve this question

edited 3 mins ago

200_success

131k17156422

asked 2 hours ago

user644361user644361

604

New contributor

user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is std::thread right redundant?
  $endgroup$
  – user644361
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've tested: merge_sort runs faster without threading right, so it's better to only thread left and let right run in the main thread.
  $endgroup$
  – user644361
  1 hour ago
  

  
  
  
  

add a comment | 

2

$begingroup$

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:

template<typename T>
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;

function merge_sort:

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]

c++ beginner multithreading sorting mergesort

share|improve this question

edited 3 mins ago

200_success

131k17156422

asked 2 hours ago

user644361user644361

604

New contributor

user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is std::thread right redundant?
  $endgroup$
  – user644361
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've tested: merge_sort runs faster without threading right, so it's better to only thread left and let right run in the main thread.
  $endgroup$
  – user644361
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

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:

template<typename T>
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;

function merge_sort:

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]

c++ beginner multithreading sorting mergesort

share|improve this question

edited 3 mins ago

200_success

131k17156422

asked 2 hours ago

user644361user644361

604

New contributor

user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

template<typename T>
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;

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);
 

share|improve this question

edited 3 mins ago

200_success

131k17156422

asked 2 hours ago

user644361user644361

604

New contributor

user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 3 mins ago

200_success

131k17156422

asked 2 hours ago

user644361user644361

604

New contributor

user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 3 mins ago

200_success

131k17156422

edited 3 mins ago

200_success

131k17156422

asked 2 hours ago

user644361user644361

604

New contributor

user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 hours ago

user644361user644361

604