( ( ( ( ( applying heapify procedure to index ( ( ( ( ( the heapify procedure calls itself recursively to build heap in top down manner radix sort the lower bound for comparison based sorting algorithm (merge sortheap sortquick-sort etcis (nlogn) they cannot do better than nlogn counting sort is linear time sorting algorithm that sort in ( +ktime when elements are in range from to what if the elements are in range from to we can' use counting sort because counting sort will take ( which is worse than comparison based sorting algorithms can we sort such an array in linear timeradix sort is the answer the idea of radix sort is to do digit by digit sort starting from least significant digit to most significant digit radix sort uses counting sort as subroutine to sort