Make C# ParallelEnumerable.OrderBy stable sort

Question

I'm sorting a list of objects by their integer ids in parallel using OrderBy. I have a few objects with the same id and need the sort to be stable.

According to Microsoft's documentation, the parallelized OrderBy is not stable, but there is an implementation approach to make it stable. However, I cannot find an example of this.

var list = new List<pair>() { new pair("a", 1), new pair("b", 1), new pair("c", 2), new pair("d", 3), new pair("e", 4) };
var newList = list.AsParallel().WithDegreeOfParallelism(4).OrderBy<pair, int>(p => p.order);

private class pair {
  private String name;
  public int order;

  public pair (String name, int order) {
    this.name = name;
    this.order = order;
  }
}

Answer 1

The remarks for the other OrderBy method suggest this approach:

var newList = list
   .Select((pair, index) => new { pair, index })
   .AsParallel().WithDegreeOfParallelism(4)
   .OrderBy(p => p.pair.order)
   .ThenBy(p => p.index)
   .Select(p => p.pair);