1

I have an assignment and i need working code. Before i start i want to understand the problem but i cant figure out how to write it.

I have an array of data, 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, throw it into a thread pool and do that recursively until i have <=2 elements. If i have 2 elements i need to check which is less and put it on the left side then return the array.

What i don't understand is how do i merge the array? am i suppose to split the array, throw a thread into the pool and block until its ready? How do i get the results of the thread? I'm going to assume its not possible to merge the arrays without blocking?

Heres what i have so far.

 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 prof did say we can ask others for help. I think i can solve this without asking but i want to get the best answer. Threading is my weakness (i dont everything else, db, binary io, web interface, just never complex threads)

Improve this question
3
  • Do you know any sorting algorithms? Which ones do you think are amenable to parallel execution? Have you tried a web search? Why do you have code before having an algorithm? Commented Jan 12, 2011 at 20:48
  • @David Hefferna. 1) I used to, in HS. 2) I dont know/remember any. 3) Yes 4) From i understand i am to learn threads so i am to use this algorithms. Commented Jan 12, 2011 at 21:02
  • I think you need to learn how to do a web search before you tackle this problem. A search for parallel sort will get you plenty of information. Commented Jan 12, 2011 at 21:19

3 Answers 3

Reset to default
2

This appears to be a parallel version of merge sort. You should essential make it work like the recursive sequential version, but apparently run each recursive sort as a separate task.

In your task API, there should be some way to wait for completion, and perhaps to also pass results. With that, you can copy the traditional mergesort fairly well: for each sub-sort, put a task into the pool, and wait for completion of the two subtasks. Then perform the merge, and pass back your own result to your calling tasking.

If you have a regular thread API only (i.e. no real task library), then I suggest you provide the output in a 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 task completion by joining the two subthreads.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

To add onto 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.

Improve this answer

1 Comment

Thinking about this, i could modify the array without problems. +1.
0

More than happy to oblige: Any multi-core sorting implementation in .NET?

Improve this answer

Comments