It is well accepted that processing sorted arrays is easier and efficient. What would be the pedagogical approach to explain how and why it is more efficient to process sorted collections than unsorted collections.

  • Hi m__, welcome to Computer Science Educators. What do you mean by "process", and what age/level are you teaching to? Without some further details, I'm afraid @KimNguyễn's response of "no it's not" is about as far as we can help you. – Ben I. Dec 3 at 11:33
up vote 5 down vote accepted

First, it is not "well accepted" that processing sorted array is more efficient. It depends on what you do. If you spend your time inserting, for instance, then sorted arrays are not necessarily a good choice. You are better off inserting at the end (say if you have resizable arrays such as Vector<X> or ArrayList<X> in Java), and then sort afterwards (you'll pay $O(N*log(N))$ instead of $O(N²)$).

It is true that if you don't have insertions (or very few insertions with respect to searching or other operations for instance) then it is more efficient. If you want to find an element in a sorted array, you can use binary search which is $O(log(N))$ while if your array is not sorted you have to scan the whole thing which is $O(N)$.

Likewise if you want to perform set operations on two sorted arrays (intersection, union, difference), then doing so on sorted Arrays is linear. If they are not sorted you will be either quadratic (naive algorithm) or have to use an auxiliary data structure (such as a hash table).

Sorted arrays have the same complexity for these operations than the more involved tree structures (AVL or red-black trees) and they have a very compact and simple representation. But you pay the price that insertion is more expensive, since it has to maintain the order of elements.

  • Inserting in a sorted list can be done in O(n), in fact this is an example where a sorted list helps. Only Insertion Sort takes O(n²) – OBu Dec 3 at 11:32
  • 1
    That's my point. If your use case is to insert a lot of values, and have the result sorted at the end it is better to insert at the end of the array (constant time for the structures I mention) and sort everything afterwards. Other wise the whole process takes O(N²) (N is the number of elements inserted). Of course the insertion of a single element is linear. Also, OP asks specifically about arrays. In that case, insertion also needs to move the rest of the elements to the right (which is also linear). So again, it all depends on your use case. – Kim Nguyễn Dec 3 at 11:50
  • @OBu, inserting in a sorted linked list can be done in O(n), but "List" does not always mean LinkedList. – Solomon Slow Dec 3 at 19:14
  • @SolomonSlow The same holds true for an array implementation. – OBu Dec 3 at 21:32
  • 1
    @OBu inserting n element in to a list $O(n^2)$. Kim is discussing inserting lots of elements, not just one. – ctrl-alt-delor Dec 5 at 8:35

I would do it unplugged. Give then a sorted stack of cards, get them to find a number. Repeat with an unsorted list.

Ensure that there are gaps, not a sequence, but sorted. I got caught out with this, pupils could find a card in a sequence in $O(1)$.

If an array is unsorted, and you want to check an item for membership in it, that is O(n) time procedure. If it is sorted, you can use divide-and-conquer to do this task in O(log(n) time.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.