The average time to check if a random array is sorted is e - 1. This was not the result I was expecting, but it’s also easy to check.

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int unt;

const unt length = 100;

unt
sortlen(unt *arr)
{       
        unt i;

        for (i = 0; i < length - 1; i++)
                if (arr[i] > arr[i + 1])
                        break;
        return i + 1;
}       

void
shuffle(unt *arr)
{       
        unt i;
        
        for (i = 0; i < length - 1; i++) {
                unt j = i + arc4random_uniform(length - i);
                unt t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
        }       
}       

int
main(int argc, char **argv)
{       
        const unt trials = 1000000;
        unt arr[length];
        unt i;
        unt count = 0;
        
        for (i = 0; i < length; i++)
                arr[i] = i;
        
        for (i = 0; i < trials; i++) {
                shuffle(arr);
                count += sortlen(arr);
        }       
        printf("avg sort len %f\n", (double)count / trials);
}       

And the results:

carbolite:/tmp> ./sort                 
avg sort len 1.718539
carbolite:/tmp> ./sort 
avg sort len 1.717483
carbolite:/tmp> ./sort 
avg sort len 1.718032

I’m not sure if it’s reasonable to expect the inputs to such a function to be uniformly random arrays. Any program which checks if an array is sorted probably deals with sorted arrays more frequently. But at least the math checks out.