Can partial sorting help with lookup cost in arrays?

Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(\log(n))$. That means it is sometimes worthwhile to sort an array. However, that is a trade-off as a sorting algorithm has a time complexity of $O(n\log(n))$.

As far as I know, you can not sort an array in less than $O(n\log(n))$ time. I am however wondering if there is any algorithm that can partially sort the array in less time than that? I am pretty sure you can not look up a value in such a partially sorted array in $O(\log(n))$ time, but can you do better than $O(n)$?

In short, is it possible to process an unsorted array with an algorithm faster than $O(n\log(n))$ such that a lookup algorithm can do a search faster than $O(n)$, though not as fast as $O(\log(n))$?

• I am aware that there may be a very basic error or misconception in there somewhere, I am not and have never studied computer science, and I am not comfortable with the $O$ notation. Sep 20 '16 at 21:12
• You can sort a list in $O(n\log n)$ time. Sep 20 '16 at 21:19
• It is a bit unclear what exactly you are looking for, but take a quicksort - median pivoted version (guaranteed to work in nlogn in exchange for median overhead. Now take half of the steps. What that gives you? Data is partitioned, and in the every partition elements are not far from the sorted index but during lookup you have to traverse a partition.
– Evil
Sep 20 '16 at 22:05
• Please define what exactly you mean by "partially sorted". There are many competing notions of sortedness in the literature.
– Raphael
Sep 20 '16 at 23:21
• "Is it possible to process an unsorted array with an algorithm faster than O(nlog(n)) such that a lookup algorithm can do a search faster than O(n)" Maybe. "Can partial sorting help with lookup cost in arrays?" Absolutely not (for a single lookup). Sep 21 '16 at 1:17

If you run "balanced Quicksort" (using the exact median at every step) up to depth $k$ (at the cost of $O(n k)$), you get a partition of the original array into $2^k$ sorted parts of $n/2^k$ unsorted elements each. Given an element, we can locate the correct part in time $O(\log(2^k)) = O(k)$ using binary search, and then look it up using an additional $O(n/2^k)$, for a total complexity of $O(n/2^k + k)$.
If $k = o(\log n)$ then the partial sorting takes time $o(n\log n)$. If $k = \omega(1)$ then the lookup algorithm takes time $o(n)$. Thus if $1 \ll k \ll \log n$ we get $o(n\log n)$ preprocessing time and $o(n)$ lookup time. For example, if $k = \log\log n$ then preprocessing takes $O(n\log\log n)$ and lookup takes $O(n/\log n)$.