Fastest way to check if an array is sorted

user_369619 0
Viewed 36578

Considering there is an array returned from a function which is of very large size.

What will be the fastest approach to test if the array is sorted?

A simplest approach will be:

/// <summary>
/// Determines if int array is sorted from 0 -> Max
/// </summary>
public static bool IsSorted(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
    if (arr[i - 1] > arr[i])
    {
    return false;
    }
}
return true;
}
sorting algorithm .net c#
9 Answers

Here is my version of the function IsSorted

public static bool IsSorted(int[] arr)
{               
    int last = arr.Length - 1;
    if (last < 1) return true;

    int i = 0;

    while(i < last && arr[i] <= arr[i + 1])
        i++;

    return i == last;
}

While this function is a bit faster than in the question, it will do fewer assignments and comparisons than anything has been posted so far. In the worst case, it does 2n+1 comparisons. It still can be improved if you can make a reasonable assumption about the nature of the data like minimum data size or array contains even number of elements.

user_3051970

If the order doesn't matter(descending or ascending).

private bool IsSorted<T>(T[] values) where T:IComparable<T>
{
    if (values == null || values.Length == 0) return true;

    int sortOrder = 0;

    for (int i = 0; i < values.Length - 1; i++)
    {
        int newSortOrder = values[i].CompareTo(values[i + 1]);

        if (sortOrder == 0) sortOrder = newSortOrder;

        if (newSortOrder != 0 && sortOrder != newSortOrder) return false;
    }

    return true;
}
user_33117990
Related