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 *
--
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.
