title: Bitonic Sort in Multithread (threads conflict)?
body: <p>I have a problem with the correct sorting using multithreading. Bitonic sorting works correctly in a SingleThread, but in MultiThread returns not quite the correct result. What can be a problem? I suspect that this may be some conflict of threads (race condition)?</p>
  
  <pre><code>public class MultiThreadedSorter : BaseBitonicSorter
  {
      private int minimumLength = 1;
  
      public override void Sort(ref int[] array)
      {
          a = array;
          minimumLength = a.Length / Environment.ProcessorCount; // przydział procesów
          BitonicSort(new BitonicParameters(0, a.Length, Ascending));
      }
  
      private void BitonicSort(object AsyncState)
      {
          BitonicParameters parameters = (BitonicParameters)AsyncState;
          if (parameters.Length &gt; 1)
          {
              if (parameters.Length &gt; minimumLength)
              {
                  int median = parameters.Length / 2;
                  Thread left = new Thread(BitonicSort);
                  Thread right = new Thread(BitonicSort);
                  left.Start(new BitonicParameters(parameters.Index, median, Ascending));
                  right.Start(new BitonicParameters(parameters.Index + median, median, Descending));
                  left.Join();
                  right.Join();
              }
              else
              {
                  int median = (parameters.Length / 2);
                  if (median &gt; 1)
                  {
                      BitonicSort(new BitonicParameters(parameters.Index, median, Ascending));
                      BitonicSort(new BitonicParameters(parameters.Index, median, Ascending));
                  }
              }
              BitonicMerge(new BitonicParameters(parameters.Index, parameters.Length, parameters.Direction));
          }
      }
  
      private void BitonicMerge(object AsyncState)
      {
          BitonicParameters parameters = (BitonicParameters)AsyncState;
          if (parameters.Length &gt; 1)
          {
              if (parameters.Length &gt; minimumLength)
              {
                  int median = (parameters.Length / 2);
  
                  for (int i = parameters.Index; i &lt; (parameters.Index + median); i++)
                  {
                      Compare(i, (i + median), parameters.Direction);
                  }
                  Thread left = new Thread(BitonicMerge);
                  Thread right = new Thread(BitonicMerge);
                  left.Start(new BitonicParameters(parameters.Index, median, parameters.Direction));
                  right.Start(new BitonicParameters(parameters.Index + median, median, parameters.Direction));
                  left.Join();
                  right.Join();
              }
              else
              {
                  int median = (parameters.Length / 2);
  
                  for (int i = parameters.Index; i &lt; (parameters.Index + median); i++)
                  {
                      Compare(i, (i + median), parameters.Direction);
                  }
                  if (median &gt; 1)
                  {
                      BitonicMerge(new BitonicParameters(parameters.Index, median, parameters.Direction));
                      BitonicMerge(new BitonicParameters(parameters.Index + median, median, parameters.Direction));
                  }
              }
          }
      }
  
      private struct BitonicParameters
      {
          public BitonicParameters(int index, int length, bool direction)
          {
              Index = index;
              Length = length;
              Direction = direction;
          }
          public int Index;
          public int Length;
          public bool Direction;
      }
  }
  
  public class SingleThreadedBitonicSorter : BaseBitonicSorter
  {
  
      public override void Sort(ref int[] array)
      {
          a = array;
          BitonicSort(0, a.Length, Ascending);
      }
  
      private void BitonicSort(int index, int length, bool direction)
      {
          if (length &gt; 1)
          {
              int median = (length / 2);
              if (median &gt; 1)
              {
                  BitonicSort(index, median, Ascending);
                  BitonicSort(index + median, median, Descending);
              }
              BitonicMerge(index, length, direction);
          }
      }
  
      private void BitonicMerge(int index, int length, bool direction)
      {
          if (length &gt; 1)
          {
              int median = (length / 2);
  
              for (int i = index; i &lt; (index + median); i++)
              {
                  Compare(i, (i + median), direction);
              }
              if (median &gt; 1)
              {
                  BitonicMerge(index, median, direction);
                  BitonicMerge((index + median), median, direction);
              }
          }
      }
  }
  </code></pre>