C#

<pre>using System;

namespace DoublyLinkedList
{
	class Link<T> : IComparable<Link<T>> where T : IComparable<T>
	{
		public Link(T data)
		{
			Data = data;
			Next = null;
			Previous = null;
		}
		public T Data {get;set;}
		public Link<T> Next {get;set;}
		public Link<T> Previous {get;set;}
		public int CompareTo(Link<T> other) {return Data.CompareTo(other.Data);}
		public int CompareTo(T other) {return Data.CompareTo(other);}
		public void DisplayLink()
			{Console.Write(Data.ToString() + " ");}
	}
}

<pre>using System;

namespace DoublyLinkedList
{
	class DoublyLinkedList<T> where T :IComparable<T>
	{
		public Link<T> First {get;set;}
		public Link<T> Last {get;set;}
		public DoublyLinkedList() {First = null;Last = null;}
		public Link<T> Find(T key)
		{
			Link<T> current = First;
			while(current.CompareTo(key) != 0)
			{
				if(current.Next == null)
					return null;
				else
					current = current.Next;
			}
			return current;
		}
		public bool IsEmpty()
			{return First == null;}
		public void InsertFirst(T dd)
		{
			Link<T> NewLink = new Link<T>(dd);
			if(IsEmpty())
				Last = NewLink;
			else
				First.Previous = NewLink;
			NewLink.Next = First;
			First = NewLink;
		}
		public void InsertLast(T dd)
		{
			Link<T> NewLink  = new Link<T>(dd);
			if(IsEmpty())
				First = NewLink;
			else
			{
				Last.Next = NewLink;
				NewLink.Previous = Last;
			}
			Last = NewLink;
		}
		public Link<T> DeleteFirst()
		{
			if(IsEmpty())
				return null;
			Link<T> temp = First;
			if(First.Next == null)
				Last = null;
			else
				First.Next.Previous = null;
			First = First.Next;
			return temp;
		}
		public Link<T> DeleteLast()
		{
			if(IsEmpty())
				return null;
			Link<T> temp = Last;
			if(First.Next == null)
				First = null;
			else
				Last.Previous.Next = null;
			Last = Last.Previous;
			return temp;
		}
		public bool InsertAfter(T key,T dd)
		{
			Link<T> current = Find(key);
			if(current == null)
				return false;
			Link<T> NewLink = new Link<T>(dd);
			NewLink.Next = current.Next;
			if(current.Next == null)
				Last = NewLink;
			else
				current.Next.Previous = NewLink;
			NewLink.Previous = current;
			current.Next = NewLink;
			return true;
		}
		public Link<T> DeleteKey(T key)
		{
			Link<T> current = Find(key);
			if(current == null)
				return null;
			if(current.Previous == null)
				First = current.Next;
			else
				current.Previous.Next = current.Next;
			if(current.Next == null)
				Last = current.Previous;
			else
				current.Next.Previous = current.Previous;
			return current;
		}
		public void DisplayForward()
		{
			Console.Write("List (first-->last): ");
			Link<T> current = First;
			while(current != null)
			{
				current.DisplayLink();
				current = current.Next;
			}
			Console.WriteLine("");
		}
		public void DisplayBackward()
		{
			Console.Write("List (last-->first): ");
			Link<T> current = Last;
			while(current != null)
			{
				current.DisplayLink();
				current = current.Previous;
			}
			Console.WriteLine("");
		}
		// Functions for sorting
		public void Split(ref DoublyLinkedList<T> L1,ref DoublyLinkedList<T> L2)
		{
			Link<T> p = First;
			Link<T> q = Last;
			while(p != q && p.Next != q)
			{
				p = p.Next;
				q = q.Previous;
			}
			if(p == null || p.Next == null)
			{
				L1.First = First;
				L1.Last = Last;
				L2.First = null;
				L2.Last = null;
			}
			else
			{
				q = p.Next;
				p.Next = null;
				q.Previous = null;
				L1.First = First;
				L1.Last = p;
				L2.First = q;
				L2.Last = Last;
			}
		}
		public void Merge(DoublyLinkedList<T> L1,DoublyLinkedList<T> L2)
		{
			Link<T> p,q;
			First = null;
			Last = null;
			// Assume that both lists ars non empty and set head of result list 
			if(L1.First != null && L2.First != null)
			{
				if(L1.First.CompareTo(L2.First) <= 0) 
				{
					p = L1.First;
					if(L1.First.Next == null)
						L1.Last = null;
					else
						L1.First.Next.Previous = null;
					L1.First = L1.First.Next;
					p.Next = null;
					First = p;
					Last = p;
				}
				else
				{
					q = L2.First;
					if(L2.First.Next == null)
						L2.Last = null;
					else
						L2.First.Next.Previous = null;
					L2.First = L2.First.Next;
					q.Next = null;
					First = q;
					Last = q;
				}
			}
			/* Compare key values from current nodes of both linked list 
			   and append node with less key value to result list */
			while(L1.First != null && L2.First != null)
			{
				if(L1.First.CompareTo(L2.First) <= 0)
				{
					p = L1.First;
					if(L1.First.Next == null)
						L1.Last = null;
					else
						L1.First.Next.Previous = null;
					L1.First = L1.First.Next;
					p.Next = null;
					Last.Next = p;
					p.Previous = Last;
					Last = p;
				}
				else
				{
					q = L2.First;
					if(L2.First.Next == null)
						L2.Last = null;
					else
						L2.First.Next.Previous = null;
					L2.First = L2.First.Next;
					q.Next = null;
					Last.Next = q;
					q.Previous = Last;
					Last = q;
				}
			}
			// Concatenate rest of the list to result list;	
			if(Last != null)
				Last.Next = L1.First;
			else
				First = L1.First;
			if(L1.First != null)
			{
				L1.First.Previous = Last;
				Last = L1.Last;
			}
			if(Last != null)
				Last.Next = L2.First;
			else
				First = L2.First;
			if(L2.First != null)
			{
				L2.First.Previous = Last;
				Last = L2.Last;
			}
		}
		public void MergeSort()
		{
			DoublyLinkedList<T> h1 = new DoublyLinkedList<T>();
			DoublyLinkedList<T> h2 = new DoublyLinkedList<T>();
			if(First != null && First.Next != null)
			{
				Split(ref h1,ref h2);
				h1.MergeSort();
				h2.MergeSort();
				Merge(h1,h2);
			}
		}
	}
}