Merge sort is often the best choice for sorting a linked list. Reason because it requires only Θ(1) extra space only and generally beats other algorithms like quicksort,heapsort for sorting linked lists. The overall complexity remain O(N log N) even in the worst case
On 6/23/11, Anantha Krishnan <ananthakrishnan....@gmail.com> wrote: > Hi All, > > Can someone explain about the time complexity of Merge sort(Linked list with > billions of node)? > > There is no way to find the middle of sub-list without traversing > completely. > > Please clear my doubts. > > Thanks & Regards, > Anantha Krishnan > > -- > 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. > > -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=100000655377926 * -- 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.
