Order statistics Select the ith smallest of n elements( the element with rank i) i=l: minimum i-n.mimu i=L(n+1)2] or[(n+1)/2 median Naive algorithm: Sort and index ith element Worst-case running time=o(n Ig n)+O(1) o(n Ig n) using merge sort or heapsort(not quicksort) o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.2 Order statistics Select the ith smallest of n elements (the element with rank i). • i = 1: minimum; • i = n: maximum; • i = (n+1)/2 or (n+1)/2: median. Naive algorithm: Sort and index ith element. Worst-case running time = Θ(n lg n) + Θ(1) = Θ(n lg n), using merge sort or heapsort (not quicksort)