C# sort with Comparer is giving incorrect result

Question

class Solution {

    List<List<int>> ans = new List<List<int>>();

    public List<List<int>> subsets(List<int> A) {

        var currList = new List<int>();
        A.Sort();
        GenerateSubSets(A, 0, currList);
        ans.Sort(new ListComparer());
        return ans;
    }

    public void GenerateSubSets(List<int> A, int position, List<int> currList)
    {
        if(position > A.Count-1)
        {
            ans.Add(currList);
            return;
        }
    
        GenerateSubSets(A, position+1, new List<int>(currList));
        currList.Add(A[position]);
        GenerateSubSets(A, position+1, new List<int>(currList));

        return; 
    }
}

public class ListComparer : IComparer<List<int>>
{
    public int Compare(List<int> list1, List<int> list2)
    {
        var list1Index = 0;
        var list2Index = 0;

        while((list1Index < list1.Count) && (list2Index < list2.Count))
        {
            if(list1[list1Index].CompareTo(list2[list2Index]) == 0)
            {
                list1Index++;
                list2Index++;
                continue;
            }
            return list1[list1Index].CompareTo(list2[list2Index]);
        }
        return list1.Count > list2.Count ? 1 : -1; 
    }
}

The above code when run for test case

[ 8, 5, 19, 11, 10, 7, 18, 16, 13, 17 ]

gives me incorrect answer.

Instead of getting

... [5 10 16 17 ] [5 10 16 17 18 ] ...

I get

... [5 10 16 17 18 ] [5 10 16 17 ] ...

Except for this line all other comparisons seems to be working fine. Also, if I call the sort function twice,

ans.Sort(new ListComparer())

this issue goes away. What am I missing? I am running this code in a leetcode style editor.

Answer 1

It seems that you want something like this:

public class ListComparer : IComparer<List<int>> {
  public int Compare(List<int> left, List<int> right) {
    // Compare with itself is always 0
    if (ReferenceEquals(left, right)) 
      return 0; 

    // Let null be less than any list
    if (left == null)
      return -1;
    if (right == null)
      return 1;

    // Compare corresponding items
    for (int i = 0; i < Math.Min(left.Count, right.Count); ++i) {
      int result = left[i].CompareTo(right[i]);

      // items are not equal; we can return the result here
      if (result != 0)
        return result;
    }
     
    // All corresponding items are equal
    // Let longer list be greater
    return left.Count.CompareTo(right.Count); 
  }
}

You can generalize the solution (what if you want to use an array, not list? long instead of int?):

public sealed class SequenceComparer<T> : IComparer<IEnumerable<T>> 
  where T : IComparable<T> {
  
  public int Compare(IEnumerable<T>? left, IEnumerable<T>? right) {
    if (ReferenceEquals(left, right))
      return 0;
    if (left is null)
      return -1;
    if (right is null)
      return +1;

    var comparer = Comparer<T>.Default;

    using var leftEn = left.GetEnumerator();
    using var rightEn = right.GetEnumerator();

    while (true) {
      if (leftEn.MoveNext())
        if (rightEn.MoveNext()) {
          int result = comparer.Compare(leftEn.Current, rightEn.Current);

          if (result != 0)
            return result;
        }
        else
          return 1;
      else if (rightEn.MoveNext())
        return -1;
      else
        return 0;
    }
  }
}