CODEWITHSUNDEEP
multithreadingsorting
user34537
user34537

Reputation:

Sort with threads

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)

Upvotes: 1

Views: 3173

Answers (3)

Jesse C. Slicer
Jesse C. Slicer

Reputation: 20157

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

Upvotes: 0

David Weiser
David Weiser

Reputation: 5195

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.

Upvotes: 2

Martin v. L&#246;wis
Martin v. L&#246;wis

Reputation: 127467

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.

Upvotes: 2

Related Questions