Sort with threads

Question

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)

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? — David Heffernan, Jan 12 '11 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. — , Jan 12 '11 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. — David Heffernan, Jan 12 '11 at 21:19

score 2 · Accepted Answer · answered Jan 12 '11 at 21:04

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.

score 2 · Answer 2 · answered Jan 12 '11 at 21:24

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.

answered Jan 12 '11 at 21:24

David Weiser

5,190
4
28
35

Thinking about this, i could modify the array without problems. +1. – Jan 12 '11 at 21:32

score 0 · Answer 3 · edited May 23 '17 at 12:14

0

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

edited May 23 '17 at 12:14

Community

1
1

answered Jan 12 '11 at 21:55

Jesse C. Slicer

19,901
3
68
87

Sort with threads

3 Answers3

Linked