Sort by topic

Question

I have a task and I need a working code. Before I start, I want to understand the problem, but I cannot figure out how to write it.

I have a data array, take this for example

var arr = new byte[] {5,3,1,7,8,5,3,2,6,7,9,3,2,4,2,1} 

I need to split this array in half, drop it into the thread pool and do it recursively until I have <= 2 elements. If I have 2 elements, I need to check which is smaller and put them on the left side and then return the array.

What I do not understand how to combine an array? I suppose to split the array, throw the thread into the pool and block it until ready? How to get stream results? Am I going to suggest that it is not possible to combine arrays without locking?

Here is what I still have.

  static void Main(string[] args) { var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 }; var newarr = Sort(arr); Console.Write(BitConverter.ToString(newarr)); } static byte[] Sort(byte[] arr) { if (arr.Length <= 2) return arr; if (arr.Length == 2) { if (arr[0] > arr[1]) { var t = arr[0]; arr[0] = arr[1]; arr[1] = t; } return arr; } var arr1 = arr.Take(arr.Length / 2).ToArray(); var arr2 = arr.Skip(arr1.Count()).ToArray(); //?? return arr; } 

Note. The professor said that we can ask others for help. I think I can solve this without asking, but I want a better answer. Threading is my weakness (I'm not everything else, db, binary io, web interface, just never complex threads)

Answer 1

This seems to be a parallel version of merge sort . You have to make it work as a recursive sequential version, but apparently perform each recursive view as a separate task.

There should be some way in your task API to wait for completion, and possibly also pass the results. At the same time, you can copy the traditional merge system pretty well: for each auxiliary sorting, put the task in the pool and wait for the completion of two subtasks. Then merge and return your own result to your task.

If you have only an API with a normal thread (i.e. there is no real library of tasks), I suggest you provide the output in the third array: each thread will have two input arrays and one output array. If you are allowed to create fresh threads for each task, you can wait for the task to complete by attaching two routines.

Answer 2

To add Martin's answer, I would not create smaller copies of the array. Instead, I would have each thread work on a subset of the original array.

Answer 3

More than happy to oblige: Any multicore sort implementation in .NET?