When is it worth to sort an array? [closed]

Question

Years ago, in a job interview, I was asked: When is it worth to sort an array? I remember not being able to answer properly, recently I did an algorithm course, and I come to the conclusion that providing a more "academical" response would have probably got me that job... anyway, it is not possible to fix the past, so far I am trying to formally answer it to myself, currently, this is where I am:

Given an array, the time to search will be

• O(n) if not sorted
• O(log(n)) if sorted

Considering that quick sort sorts in O(n*log(n))

When is it worth to sort an array? It would of course depend on the number of times we are going to search the array.

• Cost of searching x times in sorted array = O(n*log(n)) + [O(log(n)) * x]
• Cost of searching x times in unsorted array = O(n) * x

What would be the value of x?

Answer 1

Personally I would answer, that it is worth sorting an array if any of the following is true:

• we plan to often ask for the biggest value in the array (cut cost from O(n) to O(1)),
• we plan to often ask for the smallest value in the array (cut cost from O(n) to O(1)),
• we will often seek for a given value in the array (cut cost from O(n) to O(log(n)).

If it is possible to sort the array in O(n) (for ex., the data fulfills the criteria for counting sort) we would start gaining from search operation (so the total time, including time necessary for sorting, will be smaller than time taken by searching in an unsorted array) after k operations, where k = constantOfSortingOperation / (n/log(n)) (time it took to sort the array divided by gain from searching the sorter array).

If we sort the array in O(nlogn), using for ex. HeapSort or QuickSort (where the constant hidden in big-O notation is small) we would start gaining from search operation after k = (constant*nlogn)/ (n/logn). constant/nlogn is basically how many Times could we search the unsorted array if we spend the time not on sorting, but on searching. n/logn is how much we gain from a single search in a sorter array compared to search in an unsorted array. So if we consider our constant to be small (much smaller than n) the time after we start gaining (= x, more or less) would be approximately n*logn * logn / n = (log(n))^2.

If we include calculations of gains from getting the biggest/smallest value, we start gaining from sorting an array much faster.