I am practicing about threads and concurrency in C# and tried to implement the basic odd-even sort algorithm using a thread for even and another for odd sorting.

static bool Sort(int startPosition, List<int> list)
        {
            bool result = true;
            do
            {
                for (int i = startPosition; i <= list.Count - 2; i = i   2)
                {
                    if (list[i] > list[i   1])
                    {
                        int temp = list[i];
                        list[i] = list[i   1];
                        list[i   1] = temp;
                        result = false;
                    }
                }
            } while (!result);
            return result;
        }

While the main method is like this:

static void Main(string[] args)
        {
            bool isOddSorted = false;
            bool isEvenSorted = false;

            List<int> list = new List<int>();
            while (list.Count < 15)
            {
                list.Add(new Random().Next(0, 20));
            }

            var evenThread = new Thread(() =>
            {
                isEvenSorted = Sort(0, list);
            });
            evenThread.Start();

            var oddThread = new Thread(() =>
            {
                isOddSorted = Sort(1, list);
            });
            oddThread.Start();

            while (true)
            {
                if (isEvenSorted && isOddSorted)
                {
                    foreach (int i in list)
                    {
                        Console.WriteLine(i);
                    }
                    break;
                }
            }

        }

Understandably, the loop in Sort method works forever because the result variable is never set to true. However the way it works manages to sort the list. It just doesn't break at any time.

However the moment I add a "result = true" to the first line of do-scope of Sort function, the sorting messes up.

I couldn't figure out how to fix this.

CodePudding user response：

You cannot do odd-even sort easily in a multi-threaded manner. Why? Because the odd-even sort is in essence the repetition of two sorting passes (the odd and the even pass), with any subsequent pass depending on the result of the preceding pass. You cannot run two passes in parallel/concurrently in practical terms, as each pass has to follow each other.

There are of course ways to employ multi-threading, even with odd-even-sort, although that wouldn't probably make much practical sense. For example, you could divide the list into several partitions, with each partition being odd-even-sorted independently. The sorting of each partition could be done in a multi-threaded manner. As a final step it would require merging the sorted partitions in a way that would result in the fully sorted list.

(By the way, that you eventually get a sorted list if you only let the do while loops in your Sort method run many, many times is just that given enough time, even with "overlapping" concurrent passes you reach eventually a sorted list, but maybe not with all the same numbers from the original list. Because given enough repetions of the loop, eventually the elements will be compared with each other and shuffled to the right positions. However, since you have not synchronized list access, you might lose some numbers from the list, being replaced with duplicates of other numbers, depending on the runtime behavior and timing of list accesses between the two threads.)

CodePudding user response：

You are trying to modify non-thread safe collection across threads.
Even if the assumption is good - you are using basic swap in Sort method (but you did not implement it entirely correct), you have to take under account that while one of the threads is doing the swap, other one could swap a value that is being in temp variable in this exact moment.
You would need to familiarize ourself with either locks and/or thread-Safe Collections.

CodePudding user response：

Look at your result variable and the logic you have implemented with regard to result.

The outer do ... while (!result) loop will only exit when result is being true.

Now imagine your inner for loop finds two numbers that need swapping. So it does and swaps the numbers. And sets result to false. And here is my question to you: After result has been set to false when two numbers have been swapped, when and where is result ever being set to true?

Also, while you sort each the numbers on even list positions, and each the numbers on odd positions, your code does not do a final sort across the entire list. So, basically, if after doing the even and odd sorting, a larger number on an even position n is followed by a smaller number on odd position n 1, your code leaves it at that, leaving the list essentially still (partially) unsorted...