Forcing/Requiring Sorted List Argument for Method

Question

Suppose a method has been written that expects a sorted list as one of its input. Of course this will be commented and documented in the code, param will be named "sortedList" but if someone forgets, then there will be a bug.

Is there a way to FORCE the input must be sorted? I was thinking about creating a new object class with a list and a boolean "sorted", and the passed object has to be that object, and then the method checks immediately if the "sorted" boolean is true. But I feel like there must be a better/standard way.

*This method is called in a loop, so don't want to sort inside the method.

Answer 1

Assuming that you only need to iterate this collection, and not perform any other operations, you can accept an IOrderedEnumerable, which would require that the sequence have been ordered by something. (Keep in mind that doing this may mean that it was sorted based on some other criteria than what you expected, so it's still possible that by the criteria you're using internally, the data is no sorted.)

The other option that you have is to simply sort the data after you receive it, instead of requiring the caller to sort the data. Note that for most common sorting algorithms sorting an already sorted data set is its best case speed (Typically O(n) instead of O(n*log(n))), so even if the data set is sometimes already sorted and sometimes not it's not necessarily terrible, so long as you don't have a huge data set.

Answer 2

First, let's answer the question asked here.

Is there a way to FORCE the input must be sorted?

Well, yes and no. You can specify that you need one of the data structures in .NET that has a sort order. On the other hand, no, you can't specify that it uses a sort order you care about. As such, it could be sorted by a random number, which would be the same as "unsorted" (probably) in your context.

Let me expand on that. There is no way for you to declare a type or method with a requirement that the compiler can verify that the data passed to the method is sorted according to some rules you decide upon. There simply isn't a syntax that will allow you to declare such a requirement. You either got to trust the calling code to have sorted the data correctly, or not.

So what have you got left?

My advice would be to create a method where the calling code would tell you that the data has been sorted according to some predefined requirement for calling that method. If the caller said "no, I haven't or cannot guarantee that the data is in that sort order", then you will have to sort it yourself.

Other than that you could create your own data structure that would imply the correct type of sorting.

Answer 3

It is possible to express and enforce such constraints in more powerful type systems but not in the type system of C# or .NET. You could flag the collection in some way, as you suggested, but this will not really make sure that the collections is actually sorted. You could use a boolean flag as you suggested or a special class or interface.

Personally I would not try to enforce it this way but would either check at runtime that the collection is sorted costing O(n) time. If you are iterating over the collection anyway, it would be easy to just check in every iteration that the current value is larger than the last one and throw an exception if this condition is violated.

Another option would be to use a sorting algorithm that runs in O(n) on a sorted list and just sort the collection every time. This will add not to much overhead in the case the list is really already sorted but it will still work if it is not. Insertion sort has the required property to run in O(n) on a sorted list. Bubble sort has the property, too, but is really slow in other cases.