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 K
Also u can refer
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
On 6/24/11, Piyush Sinha 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
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
pa
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
