Yes, my bad there ! Simon Tatham , creator of Putty even has a nice web
page dedicated to it :
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
Rahul: He has some C code as well , so you could plug it in where you
need it ( understanding it first, of course !)
--~--~
I agree with Googmeister since in arrays the size of arrays are fixed
we can't play wiht htem as easily as we can do with linked list. That's
why we need to copy elements to another place when Merge sort is
applied to arrays. But in linked list simle linking and de-linking
saves that extra space r
ashish wrote:
> If you have memory to spare, then you can just copy the linked list to
> an array and just do mergesort/radixsort etc. to get O(n logn) time
> complexity.
You don't need the extra memory - the beauty of mergesort
on linked lists is that it can be done in-place, stably, and
in O(
This problem is no different from sorting a single linked list as two
unsorted linked lists are essentially equivalent to one unsorted linked
list by joining their ends. So just joining the two linked lists and
sorting them will work.
If you don't want to copy the information to an array i.e. spa
I don't know what it means exactly.
But how about using the BDB(Berkely Database).
2006/5/23, Gene <[EMAIL PROTECTED]>:
Rahul K wrote:> Can somebody tell the fastest and the most optimized way to merge two> unsorted singly linked list to get a sorted linked list.
Unfortunately, Rahul, the merg
Rahul K wrote:
> Can somebody tell the fastest and the most optimized way to merge two
> unsorted singly linked list to get a sorted linked list.
Unfortunately, Rahul, the merge operation is defined only for sorted
lists. It has no meaning for unsorted lists.
You can either join the two lists i
Rahul K wrote:
> Can somebody tell the fastest and the most optimized way to merge two
> unsorted singly linked list to get a sorted linked list.
It depends on how you define "most optimized." Mergesort is a
natural candidate for sorting singly linked lists.
X-Google-Language: ENGLISH,ASCII-7-b