What is wrong with my sorting?

Question

First of all I have to specify that I'm working in Unity 5.3 and the new MonoDevelop doesn't allow me to debug. Unity just crashes :(

So I have a list of "goals" that I need to sort based on 3 criterias:

1. first should be listed the "active" goals
2. then ordered by difficulty level
3. finally randomly for goals of the same level

here is a my code:

public class Goal {
    public int ID;
    public int Level;
    public bool Active;
}

...

List<Goal> goals;

goals.Sort((a, b) => {
    // first chooses the Active ones (if any)
    var sort = b.Active.CompareTo(a.Active);
    if (sort == 0) {
        // then sort by level
        sort = (a.Level).CompareTo(b.Level);
        // if same level, randomize. Returns -1, 0 or 1
        return sort == 0 ? UnityEngine.Random.Range(-1, 2) : sort;
    } else {
        return sort;
    }
});

When I run this code sometimes I get one or more active goals after inactive ones, but I don't understand why.

Answer 1

To work correctly a sorting algorithm should not depend on mutating state. Explanation of why using a random generator while comparing values is not a good idea is given here.

The problem can be solved in two ways:

Option 1: Pre-compute random numbers

    var tmp = goals.Select( g=> new {goal = g, weight = rnd.NextDouble()})
        .OrderByDescending(t=>t.goal.Active) // Active first
        .ThenBy(t=>t.goal.Level)
        .ThenBy(t=>t.weight)
        .Select(t=>t.goal)
        .ToList();



    goals.Clear();
    goals.AddRange(tmp);

Working sample

Option 2: Sort then shuffle ties

Random rnd = new Random();

Comparison<Goal> comparison =  (a, b) => {
// first chooses the Active ones (if any)
var sort = b.Active.CompareTo(a.Active);

if (sort == 0) {
// then sort by level
    return sort = (a.Level).CompareTo(b.Level);
  } else 
{
   return sort;
}
};



int startIndex = 0;
int endIndex = 0;

goals.Sort(comparison);

while (startIndex < goals.Count)
{
    for (endIndex = startIndex + 1; endIndex < goals.Count; ++endIndex)
    {
       if (comparison(goals[startIndex], goals[endIndex]) != 0)
       {
          //End of tie
          break;
       }
    }

    if (endIndex - startIndex > 1)
    {
       // Shuffle goals of the same level
       ShuffleRange(goals, startIndex, endIndex - startIndex, rnd);
    }

    startIndex = endIndex;
}   

static void ShuffleRange<T>(List<T> list, int startIndex, int count, Random rnd)
{
     int n = startIndex + count;  
     while (n > startIndex + 1) 
     {  
        int k = rnd.Next(startIndex, n--);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}           

Working sample

Shuffle algorithm is borrowed from here