Method that recognized if a IEnumerable is sorted

Question

I have this Extension method to check if a List of any type is sorted

public static bool IsSorted<T>(this IEnumerable<T> input)
{
    IEnumerable<T> expectedListASC = input.OrderBy(x => x);
    IEnumerable<T> expectedListDESC = input.OrderByDescending(x => x);
    return expectedListASC.SequenceEqual(input) || expectedListDESC.SequenceEqual(input);
}

But with large Lists it takes time. Is there a more efficient way to get the same result?

Answer 1

Something like this ought to work:

public static bool IsSorted<T>(IEnumerable<T> input)
{
    if (input is IOrderedEnumerable<T>)
    {
        return true;
    }

    var comparer = Comparer<T>.Default;
    T previous = default(T);
    bool previousSet = false;
    bool? comparisonOrder = null;
    foreach (var value in input)
    {
        if (!previousSet)
        {
            previous = value;
            previousSet = true;
        }
        else
        {
            int comparisonResult = comparer.Compare(previous, value);
            if (comparisonResult != 0)
            {
                if (!comparisonOrder.HasValue)
                {
                    comparisonOrder = comparisonResult > 0;
                }
                else if (comparisonResult > 0 != comparisonOrder)
                {
                    return false;
                }
            }
            previous = value;
        }
    }
    return true;
}

It goes through each item whilst tracking the previous, and then uses the default comparer (as .OrderBy() would) to check if they are sorted. To allow for checking sorting in either direction, I store the result of the first non-zero comparison, and use that as a point to check.

As already noted in the comments, not all IEnumerables are re-iterable, and re-iterating those that are can be costly, depending on the implementation of what is providing the IEnumerable. Also, consider the case of an IEnumerable that returns random numbers - each time you iterate it, it would give different values (assuming the seed wasn't the same each time).

Test on a sorted list of 50,000 items (5,000 iterations) revealed that:

• Lasse's took 2137 ms to determine if it was sorted.
• My method took 2348 ms to determine if the IEnumerable was sorted.
• MineR's took 2403 ms to return a result.

Answer 2

I have included the below solution which only differs from the others in that you can specify a comparer, and it will tell you the order in which the collection is sorted.

public static class LinqHelpers
{
    [Flags]
    public enum SortDirections
    {
        NotSorted = 0,
        Ascending = 1,
        Descending = 2,
    }
    public static SortDirections GetSortDirection<T>(this IEnumerable<T> input, IComparer<T> comparer = null)
    {
        comparer = comparer ?? Comparer<T>.Default;

        bool isAsc = true;
        bool isDsc = true;
        bool isFirst = true;
        T last = default(T);
        foreach (var val in input)
        {
            if (isFirst)
            {
                isFirst = false;
            }
            else
            {
                int cmp = comparer.Compare(last, val);
                if (cmp > 0) isAsc = false;
                if (cmp < 0) isDsc = false;
            }
            if (!isAsc && !isDsc) break;
            last = val;
        }
        int result = 0;
        if (isAsc) result |= (int)SortDirections.Ascending;
        if (isDsc) result |= (int)SortDirections.Descending;
        return (SortDirections)result;
    }
}

Some edge cases:

• If 0 elements, it is considered sorted in both directions.
• If 1 element, it is considered sorted in both directions.
• If all elements are the same, it is considered sorted in both directions.

Why is yours slow for large data sets? You are sorting the data, which is O(n log n). This problem need only be O(n).

Answer 3

Here's a generic method that ought to detect whether the sequence is in increasing or decreasing order, and then checking if the rest of the collection follows suit.

It has not been fully tested, you should throw datasets to it left and right and write unit-tests if you decide to use this.

public static class CollectionExtensions
{
    public static bool IsOrdered<T>(this IEnumerable<T> collection, IComparer<T> comparer = null)
    {
        comparer = comparer ?? Comparer<T>.Default;

        bool? expectedToIncrease = null;
        using (var enumerator = collection.GetEnumerator())
        {
            bool gotFirst = enumerator.MoveNext();
            if (!gotFirst)
                return true; // empty collection is ordered
            var first = enumerator.Current;
            T second = default(T);

            while (expectedToIncrease is null)
            {
                bool gotSecond = enumerator.MoveNext();
                if (!gotSecond)
                    return true; // only equal elements are ordered
                second = enumerator.Current;

                switch (comparer.Compare(first, second))
                {
                    case int i when i < 0:
                        expectedToIncrease = false;
                        break;

                    case int i when i > 0:
                        expectedToIncrease = true;
                        break;
                }

                if (expectedToIncrease is null)
                    first = second; // prepare for next round
            }

            while (enumerator.MoveNext())
            {
                if (expectedToIncrease.GetValueOrDefault())
                {
                    if (comparer.Compare(second, enumerator.Current) < 0)
                        return false;
                }
                else
                {
                    if (comparer.Compare(second, enumerator.Current) > 0)
                        return false;
                }
            }

            return true;
        }
    }
}