Is it a bad design to expect a sorted List?

Question

Lets say I wish to solve the problem - Find maximum product of 3 numbers in an array in Java .

As its easy to solve the problem provided input List is already sorted so if my API method expects a sorted input , would that be a bad design ?

I am assuming the scenario where my API method wouldn't be controlling the source of data & input list population. That I suppose is the usual assumption when you are writing an API.

I would also assume that input could be very very large ( a million items or so ).

Is it too restrictive to impose such restrictions on upstream ?

Related Question

EDIT : I quoted that problem as an example. I meant to say, does it make more sense to keep a numerical list sorted from the very beginning ( when elements were inserted ) ? Since most problems on a collection of numbers are usually easy when collection is already sorted OR a numerical list being sorted from the very beginning of data flow has some kind of disadvantages too?

Answer 1

The JDK method Collections.binarySearch() specifies in its documentation:

The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

This of course requires that you've read and understood the prerequisites for this method. Problematic is also that in case the list isn't sorted, you don't get an error, but undefined behaviour (i.e. usually the wrong index returned). That certainly doesn't sound like good design.

However, what are the alternatives? You can't call sort() inside the method, that would be too expensive when the lists are already sorted, not to mention confusing when the side-effect of calling the method would be sorting the list.

So as you see, in some cases we need to make some prerequisites to avoid even worse design. If a programmer doesn't read the documentation, it's not really the API maker's fault. Of course you want to make your code intuitive and easy to use, but sometimes it's just not possible or realistic.

Answer 2

I think it is bad design.

Why?

@Kayaman already said, a caller providing an unsorted list will probably end up with wrong results and no hint that he did something wrong.

Second reason: You propagate an implementation detail into your API design. There could be other implementations not needing the list to be sorted (e.g. the three-numbers product can be done in O(n) on an unsorted list).

So:

• Provide a method working on an unsorted list.
• And if it's likely that your caller might have a sorted version of the list ready for you, add a second method with a name that clearly states the need for a sorted list.

Or, if from the context you are sure that the list is always sorted, then it should not be used as a plain list, but encapsulated in a class that guarantees the "sorted" property.