[algogeeks] Time Complexity of Merge Sort(Linked list)

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

Re: [algogeeks] Time Complexity of Merge Sort(Linked list)

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

Re: [algogeeks] Time Complexity of Merge Sort(Linked list)

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

Re: [algogeeks] Time Complexity of Merge Sort(Linked list)

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

Re: [algogeeks] Time Complexity of Merge Sort(Linked list)

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