title: Fast sort partially sorted array
body: <p>Firstly, it's not about an array with subsequences that may be in some order before we start sort, it's an about array of special structure.</p>
  
  <p>I'm writing now a simple method that sorts data. Until now, I used <code>Array.Sort</code>, but <code>PLINQ</code>'s <code>OrderBy</code> outperform standard <code>Array.Sort</code> on large arrays.</p>
  
  <p>So i decide to write my own implementation of multithreading sort. Idea was simple: split an array on partitions, parallel sort each partition, then merge all results in one array.</p>
  
  <p>Now i'm done with partitioning and sorting:</p>
  
  <pre><code>public class PartitionSorter
  {
      public static void Sort(int[] arr)
      {
          var ranges = Range.FromArray(arr);
          var allDone = new ManualResetEventSlim(false, ranges.Length*2);
          int completed = 0;
          foreach (var range in ranges)
          {
              ThreadPool.QueueUserWorkItem(r =&gt;
              {
                  var rr = (Range) r;
                  Array.Sort(arr, rr.StartIndex, rr.Length);
                  if (Interlocked.Increment(ref completed) == ranges.Length)
                      allDone.Set();
              }, range);
          }
          allDone.Wait();
      }
  }
  
  public class Range
  {
      public int StartIndex { get; }
      public int Length { get; }
  
      public Range(int startIndex, int endIndex)
      {
          StartIndex = startIndex;
          Length = endIndex;
      }
  
      public static Range[] FromArray&lt;T&gt;(T[] source)
      {
          int processorCount = Environment.ProcessorCount;
          int partitionLength = (int) (source.Length/(double) processorCount);
          var result = new Range[processorCount];
          int start = 0;
          for (int i = 0; i &lt; result.Length - 1; i++)
          {
              result[i] = new Range(start, partitionLength);
              start += partitionLength;
          }
          result[result.Length - 1] = new Range(start, source.Length - start);
          return result;
      }
  }
  </code></pre>
  
  <p>As result I get an array with special structure, for example</p>
  
  <pre><code>[1 3 5 | 2 4 7 | 6 8 9]
  </code></pre>
  
  <p>Now how can I use this information and finish sorting? Insertion sorts and others doesn't use information that data in blocks is already sorted, and we just need to merge them together. I tried to apply some algorithms from <code>Merge sort</code>, but failed.</p>