2

I've been trying to make an asynchronous MergeSort for fun. I quickly threw the program together before noticing that the program runs on a single thread. After a little investigation I found out that you need to use the Task.WhenAll() method. Often the place to put it was fairly obvious in the examples I've seen but with the recursive nature of my program it wasn't clear to me where to put it.

class Sorter
{
    public static async Task<List<int>> MergeSortAsync(List<int> numbersToSort)
    {
        if (numbersToSort.Count <= 1)
        {
            return numbersToSort;
        }

        var numbers1 = new List<int>();
        var numbers2 = new List<int>();

        for (int i = 0; i < numbersToSort.Count / 2; i++)
        {
            numbers1.Add(numbersToSort.ElementAt(i));
        }
        for (int i = numbersToSort.Count / 2; i < numbersToSort.Count; i++)
        {
            numbers2.Add(numbersToSort.ElementAt(i));
        }

        numbers1 = await MergeSortAsync(numbers1);
        numbers2 = await MergeSortAsync(numbers2);

        return Merge(numbers1, numbers2);
    }

    private static List<int> Merge(List<int> numbers1, List<int> numbers2)
    {
        int index1 = 0;
        int index2 = 0;
        var result = new List<int>();

        while (index1 < numbers1.Count || index2 < numbers2.Count)
        {
            if (index1 < numbers1.Count && index2 < numbers2.Count)
            {
                if (numbers1[index1] < numbers2[index2])
                {
                    result.Add(numbers1[index1]);
                    index1++;
                }
                else
                {
                    result.Add(numbers2[index2]);
                    index2++;
                }
            }
            else if (index1 < numbers1.Count)
            {
                result.Add(numbers1[index1]);
                index1++;
            }
            else if (index2 < numbers2.Count)
            {
                result.Add(numbers2[index2]);
                index2++;
            }
        }

        return result;
    }

}

Is it even possible to run a recursive method like this on multiple threads?

NoahCharef
  • 23
  • 5
  • Are you just trying to take advantage of more cores? Async/await is usually for blocking calls. – Devon Bessemer Dec 27 '21 at 15:25
  • If I run your code single-threaded (removing async/await) it works. If I modify it to make the recursive calls on separate threads (Task.Start for both, then Task.WaitAll) it does not work. The results do not come out sorted correctly. (I'm not an algorithm guy, so I just test it and see if it works.) This answer shows a multi-threaded merge sort: https://stackoverflow.com/questions/50927694/multithreading-merge-sort-how-to-optimize – Scott Hannen Dec 27 '21 at 15:58
  • That's one approach for questions like this. When in doubt, just write some tests. I wrote a few that run the sort on 100,000 random numbers and verify that the sort is correct. And I included a stopwatch so I could time both sorts. I never got as far as having to compare the times because the multithreaded sort didn't return the correct results. If it had I would have compared the times. (Some people might be able to tell if it works just by looking at it, not me.) – Scott Hannen Dec 27 '21 at 16:05
  • Converting a sorting algorithm to be asynchronous doesn't make much sense, because sorting is a CPU-bound job. Asynchrony is used with I/O-bound jobs, in order to avoid blocking needlessly a thread while the I/O-bound job is in-flight. What's interesting in your code is that the compiler doesn't emit a warning about an `async` method lacking an `await` operator, because of the recursive nature of the method (it awaits itself). – Theodor Zoulias Dec 27 '21 at 22:07
  • @TheodorZoulias I've mostly seen it in HTTP requests which fits your description but surely parallelization would give an increase in performance. This was just a small excercise to see if I can do it and I'm still not sure if it could be done. Lastly, wouldn't it still be beneficial to use async/await so it doesn't block any threads even if it isn't running in parrallel? Thanks – NoahCharef Dec 28 '21 at 07:35
  • Asynchrony and parallelism [are different things](https://stackoverflow.com/questions/4844637/what-is-the-difference-between-concurrency-parallelism-and-asynchronous-methods). Regarding using tasks for the purpose of offloading work from the current thread, this is commonly done with the `Task.Run` method. You could check [this](https://devblogs.microsoft.com/pfxteam/should-i-expose-asynchronous-wrappers-for-synchronous-methods/) article, to know what Microsoft recommends about it. – Theodor Zoulias Dec 28 '21 at 07:49

0 Answers0