I don't understand Multithreading Sort

[wariolandgoldpiramid]

I need to write a program that would do a multithread sort of an array (merge or quick), but, sadly, I do not understand much about multithreading, and how to use them, so I don't know how to turn a simple merge or quick sort into a multithread sort

[Gamer2015]

You probably need to lock it with a mutex?
I'm sorry but I don't quite understand the problem.
Do you need to sort with 2 threads (to be faster) or do you need a threadsave sort method?

[wariolandgoldpiramid]

Well, it needs to be sorted with as many threads as possible. Like, the array is devided into 2 parts, and each of those is sorted parallaly in a thread, and each of those is also devided by 2, and the 2 halfs are sorted parallaly with threads...

I just really don't understand how threads and mutexes work...

[Gamer2015]

Well, it needs to be sorted with as many threads as possible. Like, the array is devided into 2 parts, and each of those is sorted parallaly in a thread, and each of those is also devided by 2, and the 2 halfs are sorted parallaly with threads...

ah okey, so you split your array in n arrays where n in the number of cpu-cores.
What if you have an array like this and say you have 2 cores.
[8,1,5,3,2,1]
you'll get results:
[1,5,8,1,2,3]
but that's not sorted, how do you plan on merging them?

I just really don't understand how threads and mutexes work...

Then you should look for a tutorial, google will help you with that.
If you like video-tutorials here is a series of multithreading videos, his voice is annoying sometimes but I think he explains things quite good.
https://www.youtube.com/watch?v=LL8wkskDlbs

[Duthomhas]

For each sort, stick with a logarithmic algorithm. That is, both merge and quick sort algorithms are typically written by dividing an array into two parts. Don't try to divide it into more than two parts. Apply the first divide (into two parts) in the first thread, then spawn a new thread to handle one of the subarrays and use the existing thread to continue with the other. The two threads should then behave as if they have the original (complete) array (but of course they are only working on a subsection of the original array). All you need is a counter to know when to stop spawning new threads and switch over to a normal sort.

Multithreaded Merge Sort:

"Divide" your array into 2 subarrays.
Spawn a new thread. Have it sort the second subarray.
Sort the first subarray with the existing thread.
When both threads have finished, merge the final sequence.

Multithreaded QuickSort:

Apply a partition pass to sort/divide the array into 2 subarrays.
Spawn a new thread. Have it sort the second subarray.
Sort the first subarray with the existing thread.
When both threads have finished, you are done.

I can't explain this much better right now. (At least not without pretty pictures.)
Good luck!