Thanks. I think if we make k traversals at each step it would be O(n * n/2 * log n) If I know value of K we can do it in O(n log n) I agree.
What will be the time complexity if there are billion nodes i.e even if i know node count i cannot store it in integer variable? Thanks & Regards, Anantha Krishnan On Fri, Jun 24, 2011 at 12:58 AM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote: > Also u can refer > http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html > > On 6/24/11, Piyush Sinha <ecstasy.piy...@gmail.com> wrote: > > I googled a better explaination for this and found this... > > hope this will be useful... > > > > Sorting a LinkedList is different from sorting an Array as you can not > > make index based references to any arbitrary item in the List. Instead > > you need to remember the items during each recursive step and then > > pass them on to the merge function. For each recursion step you only > > need to remember the first item of each list half. If you do not > > remember these items you will quickly end up with indexes, but this > > leads you to the problem that in your merge-function you need to > > traverse the whole list with for-loops to find the items to merge. > > That in turn means you get a complexity of O(n^2). > > > > Another important point is the step of recursing into the list and > > dividing the list in two halves. You can do this step in the recursive > > part by using for-loops. Contrary to the merge-part at this step the > > for-loops will only yield a complexity of O(log(n) * n/2) and this is > > still below the overall O(n*log(n)) complexity. Here is why: > > > > 1. You always need to find the first item of each half of list part. > > 2. In the first recursion step you need to pass the first item and > > the item at position n/2. This takes n/2 steps to find. > > 3. In each following step you need to find the middle item for > > each of the two halves of the list which gives us n/4 to find the item > > in the first halve and n/4 in the other halve. In total thats n/2. > > 4. In each following recursive step the amount of list parts > > double and the lengths is divided by two: > > * 4 * n/8 in the 3rd recursion depth > > * 8 * n/16 in the 4th recursion depth, and so on... > > 5. The recursion depth is log(n) and in each step we perform n/2 > > steps. This equals O(log(n)*n/2) > > > > > > On 6/24/11, Piyush Sinha <ecstasy.piy...@gmail.com> wrote: > >> 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 * > >> > > > > > > -- > > *Piyush Sinha* > > *IIIT, Allahabad* > > *+91-8792136657* > > *+91-7483122727* > > *https://www.facebook.com/profile.php?id=100000655377926 * > > > > > -- > *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. > > -- 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.
