# How can this deterministic linear time selection algorithm be linear?

I'm trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as follows:

• Select(A,n,i)
1. If n = 1 return A[1].
2. p = ChoosePivot(A, n)
3. B = Partition(A, n, p)
4. Suppose p is the jth element of B (i.e., the jth order statistic of A). Let the “ﬁrst part of B” denote its ﬁrst j − 1 elements and the “second part” its last n − j elements.
• If i = j, return p.
• If i < j, return Select(1st part of B, j − 1, i).
• Else return Select(2nd part of B, n − j, i − j).

And sorts the array internally in the `ChoosePivot` subroutine to calculate the median of median using a comparison based sorting algorithm. But isnt the lower bound on comparison based sorting `O(nlogn)`? So how would it be possible for us to acheive `O(n)` for the entire algorithm then? Am I missing something here?

-
Are you sure that's what `ChoosePivot` does? – AakashM May 17 '12 at 9:47
Yeah `ChoosePivot` computes the median of medians of the original array for which it employs comparison based sorting, which theoretically has a worst case of `O(nlogn)` if Im not mistaken – KodeSeeker May 17 '12 at 9:55
There's no mention of sorting whatsoever. There is partitioning. Most of the array will be unsorted when the algorithm finishes. – gnasher729 Jul 7 '15 at 11:52