My addition to the algorithm: Every time your check if arrays is sorted and it isn't, start from the very beginning throwing away all progress made so far.
I doubt this way n == 6 would finish in some normal time period.
I ran it on an the array [0,1,2,3,4,5,6] and it took between 3 hundred million and 1 billion operations (by my marginally accurate counter) and between 6 and 20 minutes, but mine was in python, not C.
I was referring to OPs algorithm which was bogo-bogosort.
At first I though my change would not increase the complexity, but I think it is dependent on size of input since for every recursion there is a chance to fail and start completely over, where the number of recursion is dependent on input size. Therefore it adds to complexity.
I doubt this way n == 6 would finish in some normal time period.