I saw the question at Quora within the last few days, thought of my answer then, then seeing the question here, although just in the title, typed in my answer

I saw the question at Quora within the last few days, thought of my answer then, then seeing the question here, although just in the title, typed in my answer here just from reading the title here and not the essay. Sorry 'bout that! This question had to be the easiest question on the fastest algorithm ever! Some of the other questions at Quora were more challenging. In my answer, I improved on the question by assuming also, that, even though the array was "unsorted", really, we needed to assume more, i.e., that we knew no more about the array. E.g., the array might be unsorted but, still, in, say, as happens with some versions of the fast Fourier transform, in bit reversed order. Then there is a faster answer! The essay has a good point but is not fully correct. BTW, I prefer sequential search to linear search. That point aside, actually the essay overstates its case. E.g., in my startup I need to look at, say, 100 million numbers one at a time, where I know nothing about the order, and end up with the, say, 50 largest. So, how to do that? My solution: allocate an array x of, say, 50 components. So assume we have array components x(i) for i = 1, 2, ..., 50. Regard the array as a descending heap, that is, a heap as in heap sort and descending in the sense that x(1) is the smallest component of the array x. Of course the heap means that x(i/2) <= x(i), i = 2, 3, ..., 50. Here, of course, the i/2 is the usual result of division with integers, that is, the i/2 is the largest integer <= the fully accurate version of i/2. Sure, the 50 was just for definiteness; say the number of components in the array is positive integer m. And, let y be an array with y(j) for j = 1, 2, ..., p where p is, say, 100 million or so. Initially, just put y(j) in the heap in x for j = 1, 2, ..., m. Then in a loop for j = m + 1, m + 2,..., p, compare y(j) with x(1). If y(j) <= then x(1), then y(j) is not among the 50 largest, and we f'get about y(j). Otherwise we assign y(j) to x(1) and do a sift operation to return array x to a heap. So, when m is more than a few but not in the billions, that looks like a reasonably fast algorithm. Note that when the elements of y are just any random permutation, fairly soon the heap in array x will have relatively large components so that inserts into the heap will become relatively rare and, really, the comparison with x(1) will be all the effort needed. So, we are using the heap algorithm to build, say, a priority queue. There are other important uses in reality!