Also u can refer http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
On 6/24/11, Piyush Sinha <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
