Heapsort and any other comparison sort have a lower bound of O(nlogn). Radix sort gets around this as it isn't a comparative sorting algorithm.
It instead groups numbers by their significant digits (keeping original order), normally by count sort as mentioned above. Applying this for each significant digit will get you a sorted list in O(n) time. On 15/11/2011, Vijay Khandar <vijaykhand...@gmail.com> wrote: > How it is Radix sort, why not Heapsort, > plz explain me in detail.......... > > On Nov 14, 3:36 pm, Ankur Garg <ankurga...@gmail.com> wrote: >> Radix Sort >> >> On Mon, Nov 14, 2011 at 1:57 PM, Vijay Khandar >> <vijaykhand...@gmail.com>wrote: >> >> > Which is the sorting algm sorts the integers [1...........n^3] in >> > O(n). >> > a)Heapsort >> > b)Quicksort >> > c)Mergesort >> > d)Radix sort >> >> > please tell anyone................. >> > Vijay......... >> >> > -- >> > You received this message because you are subscribed to the Google >> > Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com. >> > For more options, visit this group at >> >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
