Native C# support for checking if an IEnumerable is sorted?

Question

Is there any LINQ support for checking if an IEnumerable<T> is sorted? I have an enumerable that I want to verify is sorted in non-descending order, but I can't seem to find native support for it in C#.

I've written my own extension method using IComparables<T>:

public static bool IsSorted<T>(this IEnumerable<T> collection) where T : IComparable<T>
{
   Contract.Requires(collection != null);

   using (var enumerator = collection.GetEnumerator())
   {
      if (enumerator.MoveNext())
      {
         var previous = enumerator.Current;

         while (enumerator.MoveNext())
         {
            var current = enumerator.Current;

            if (previous.CompareTo(current) > 0)
               return false;

            previous = current;
         }
      }
   }

   return true;
}

And one using an IComparer<T> object:

public static bool IsSorted<T>(this IEnumerable<T> collection, IComparer<T> comparer)
{
   Contract.Requires(collection != null);

   using (var enumerator = collection.GetEnumerator())
   {
      if (enumerator.MoveNext())
      {
          var previous = enumerator.Current;

         while (enumerator.MoveNext())
         {
            var current = enumerator.Current;

            if (comparer.Compare(previous, current) > 0)
                return false;

            previous = current;
         }
      }
   }

   return true;
}

Olecranon

Your check only accounts for a single direction of sorting – Wagoner

And the collection can come from anywhere? enumerables parsed with OrderBy becomes an IOrderedEnumerable – Operant

This doesn't seem to perform well. It's most probably not much faster as sorting again ... – Albuminuria

@StefanSteinegger why doesn't it perform well? It is O(n) code. – Creech

@Andrey: It doesn't perform well because it doesn't just check a property of the IEnumerable implementor. Instead, it needs to compare all items to check if the order is correct. This may be a very expensive operation. Consider that Select, Where, OrderBy and such statements may be executed just for this check. It may also trigger a lazy loading mechanism. Etc. I wonder what it could be used for anyway. – Albuminuria

@StefanSteinegger and how can be sorting is faster than that? – Creech

@Andrey: Who said this? I said that it is "probably not much faster". Which means: it is still faster, but it's probably not worth the implementation effort, maintainability cost and risk of compromising stability. – Albuminuria

@StefanSteinegger It makes absolutely no sense to sort a collection, if I want to check it the collection is sorted! I use this method for asserting my method (which returns a sorted collection) actually works. – Olecranon

@lund.mikkel: When writing a unit test, I would still use an existing sorting mechanism to create the expected result and compare it with the output of your method. – Albuminuria

@usr: IsOrdered would (or at least could) mean that it is an ordered collection like a List or Array. Sorted is the right term here. See this question: #1084646 – Albuminuria

@StefanSteinegger Why would I need that extra overhead? I don't see why I would have to create a whole new collection and sort that. I know what the sorting order is, and that is all I need. This would only take O(n) time, where the other would be at least O(n*lg(n)). – Olecranon

@lund.mikkel: Do what ever you think is appropriate. It would avoid this extra effort for test code. – Albuminuria

Don't forget to Dispose() your enumerator. – Tessler

Similar: how-to-check-if-a-list-is-ordered – Demure

Answer 1

You can check if collection is IOrderedEnumerable but that will work only if ordering is the last operation which was applied to sequence. So, basically you need to check all sequence manually.

Also keep in mind, that if sequence is IOrderedEnumerable you really can't say which condition was used to sort sequence.

---

Here is generic method which you can use to check if sequence is sorted in ascending order by field you want to check:

public static bool IsOrdered<T, TKey>(
    this IEnumerable<T> source, Func<T, TKey> keySelector)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var comparer = Comparer<TKey>.Default;
    using (var iterator = source.GetEnumerator())
    {
        if (!iterator.MoveNext())
            return true;

        TKey current = keySelector(iterator.Current);

        while (iterator.MoveNext())
        {
            TKey next = keySelector(iterator.Current);
            if (comparer.Compare(current, next) > 0)
                return false;

            current = next;
        }
    }

    return true;
}

Usage:

string[] source = { "a", "ab", "c" };
bool isOrdered = source.IsOrdered(s => s.Length);

You can create similar IsOrderedDescending method - just change checking comparison result to comparer.Compare(current, next) < 0.

Occlude

It seems like the method is overly complicated, compared to my example using a comparer (be aware that I've updated the example). This would just require you to make the comparer object as you need it. – Olecranon

@lund.mikkel your original question used IComparable type instead of comparer. Also you are forced to pass comparer to your method, it's not very convenient to use. And what exactly seems complicated to you here? I added null-check to avoid NullReferenceException if source is null and key selector, because usually you have collections sorted by some key, not by whole collection item (e.g. you have people sorted by name) – Occlude

Answer 2

There is no such built-in support.

Obviously if your IEnumerable<T> also implements IOrderedEnumerable<T> then you don't need to do an additional check, otherwise you'd have to implement an extension method like you did.

You might want to add a direction parameter or change its name to IsSortedAscending<T>, by the way. Also, there might be different properties in your T to sort on, so it would have to be obvious to you in some way what "sorted" means.

Scarito

I just updated my example to using a more general comparer. I don't think IsSortedAscending<T> makes much sense though. There is a difference between ascending and non-descending - the latter won't complain with equal objects. Your sorting order should be defined by your comparer object, making the generic name IsSorted more sensable, I think. – Olecranon

That sounds reasonable, but the fact is that you do a (comparer.Compare(current, next) > 0) check... – Scarito

Answer 3

I often find usages for an extension method I've created called SelectPairs(), and also in this case:

/// <summary>
/// Projects two consecutive pair of items into tuples.
/// {1,2,3,4} -> {(1,2), (2,3), (3,4))
/// </summary>
public static IEnumerable<Tuple<T, T>> SelectPairs<T>(this IEnumerable<T> source)
{
    return SelectPairs(source, (t1, t2) => new Tuple<T, T>(t1, t2));
}

/// <summary>
/// Projects two consecutive pair of items into a new form.
/// {1,2,3,4} -> {pairCreator(1,2), pairCreator(2,3), pairCreator(3,4))
/// </summary>
public static IEnumerable<TResult> SelectPairs<T, TResult>(
    this IEnumerable<T> source, Func<T, T, TResult> pairCreator)
{
    T lastItem = default(T);
    bool isFirst = true;
    foreach (T currentItem in source)
    {
        if (!isFirst)
        {
            yield return pairCreator(lastItem, currentItem);
        }

        isFirst = false;
        lastItem = currentItem;
    }
}

Use it like this:

bool isOrdered = myCollection
    .SelectPairs()
    .All(t => t.Item1.MyProperty < t.Item2.MyProperty);

This statement can of course be placed in another extension method:

public static bool IsOrdered<T>(
    this IEnumerable<T> source, Func<T, T, int> comparer)
{
    return source.SelectPairs().All(t => comparer(t.Item1, t.Item2) > 0);
}

bool isOrdered = myCollection
    .IsOrdered((o1, o2) => o2.MyProperty - o1.MyProperty);

Psf

Answer 4

There is a short and simple version using Zip, although your IEnumerable does get enumerated twice.

var source = Enumerable.Range(1,100000);

bool isSorted = source.Zip(source.Skip(1),(a,b)=>b>=a).All(x=>x);

Mucin

Answer 5

Here's an implementation that uses a predicate to select the value to order by.

public static bool IsOrdered<TKey, TValue>(this IEnumerable<TKey> list, Func<TKey, TValue> predicate) where TValue : IComparable
{
    if (!list.Any()) return true;
    var previous = predicate(list.First());

    foreach(var entry in list.Skip(1))
    {
        var current = predicate(entry);
        if (previous.CompareTo(current) > 0)
            return false;
        previous = current;
    }
    return true;
}

Licentious