Monday, 19 October 2009

How to implement a merge sort on a Doubly Linked List using C#

I have been working on a custom linked list recently and required a sorting algorithm to sort the doubly linked list.

Mergesort works better on linked lists than it does on arrays. It avoids the need for the auxiliary space, and becomes a simple, reliably O(N log N) sorting algorithm. And as an added bonus, it's stable too.

Here is a quick merge sort algorithm in C#.Net 3.5 (Note - T is my custom node interface) :

private T Merge_Sort(T first)

{

if (first == null || first.Next == null)

return first;


T second = Split(first);

first = Merge_Sort(first);

second = Merge_Sort(second);

return Merge(first, second);

}

private T Split(T item)

{

if (item == null || item.Next == null)

return null;

T second = item.Next;

item.Next = second.Next;


second.Next = Split(second.Next);

return second;

}

private T Merge(T first,

T second)

{

if (first == null)

return second;


if (second == null)

return first;

// If both are not null, we will run the comparer

// If first is less than second

if (first.CompareTo(second) < 0)

{

first.Next = Merge(first.Next, second);

first.Next.Previous = first;

first.Previous = default(T);


return first;

}

else

{

second.Next = Merge(first, second.Next);

second.Next.Previous = second;

second.Previous = default(T);

return second;

}

}

For the full implementation of the Custom Doubly Linked List, look at this post.

32 comments:

Anonymous said...

generic xanax xanax tumblr - xanax side effects liver

Anonymous said...

buy tramadol online tramadol hcl 50 mg overdose - tramadol withdrawal rls

Anonymous said...

xanax online xanax side effects heart - xanax online no prescription australia

Anonymous said...

tramadol online no prescription buy tramadol online usa - cheap 100mg tramadol

Anonymous said...

xanax online 2mg lorazepam vs xanax - xanax dosage recreational erowid

Anonymous said...

carisoprodol soma carisoprodol thailand - carisoprodol unrecognized drug abuse

Anonymous said...

tramadol 50mg tramadol veterinary - buy tramadol overnight no prescription

Anonymous said...

buy xanax overnight delivery how to buy xanax online for cheap - xanax effects abuse

Anonymous said...

buy tramadol online can tramadol for dogs get you high - tramadol ingredients 50 mg

Anonymous said...

buy carisoprodol carisoprodol with vicodin - drug test soma carisoprodol

Anonymous said...

buy tramadol online tramadol overnight no prescription needed - side effects to tramadol 50mg

Anonymous said...

buy tramadol online buy tramadol online free shipping - buy tramadol online usa

Anonymous said...

cialis online cialis daily for sale - cialis tablets

Anonymous said...

buy cialis online overnight shipping cialis bathtub symbolism - generic cialis fast delivery

Anonymous said...

buy tramadol online tramadol 50 mg tramadol - buy tramadol cod personal check

Anonymous said...

cialis online cialis tadalafil - cialis recommended dosage

Anonymous said...

buy cialis online buy viagra cialis cheap - buy cialis

Anonymous said...

cialis online canadian cialis reviews - buy cialis line

Anonymous said...

http://buytramadolonlinecool.com/#51726 tramadol hcl 50 mg what is it used for - tramadol addiction time

Anonymous said...

buy tramadol purchase tramadol cod - tramadol ls 100 mg

Anonymous said...

learn how to buy tramdadol tramadol depresion - tramadol lethal dose

Anonymous said...

buy tramadol online cod 50mg tramadol high dose - tramadol hcl half life

Anonymous said...

http://landvoicelearning.com/#30896 tramadol 50 mg slow release - buy tramadol online without rx

Anonymous said...

buy tramadol 100mg tramadol for ultram - tramadol withdrawal vs vicodin withdrawal

Anonymous said...

buy tramadol overnight cod tramadol withdrawal onset - tramadol 75 mg tablets

Anonymous said...

buy tramadol next day tramadol 50mg - buy tramadol online fedex delivery

Anonymous said...

generic lorazepam ativan vertigo - lorazepam 1 mg indication

Anonymous said...

http://staam.org/#56274 dangers tramadol addiction - tramadol for dogs 50mg dosage

Anonymous said...

http://staam.org/#41652 online pharmacy tramadol cheap - legal buy tramadol online usa

Anonymous said...

buy tramadol free shipping tramadol overnight delivery mastercard - tramadol 50 mg generic ultram

Anonymous said...

xanax without a perscription xanax pills photos - how many xanax pills to get high

Anonymous said...

Test