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.
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 – seeker 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