mergesort a linked list

node.py

# Python 2.7.2
class Node:
  def __init__(self, data, next=None):
    self.next = next
    self.data = data
  def __str__(self):
    if self.next == None:
      return "%d" % self.data
    else:
      return "%d => %s" % (self.data, self.next.__str__())

a1 = Node(1)
a2 = Node(2)
a3 = Node(7)
b1 = Node(9)
b2 = Node(2)
b3 = Node(10)

a1.next = a2
a2.next = a3
a3.next = b1
b1.next = b2
b2.next = b3
 

def get_mid(head, end): 
  size = 0
  current = head
  while current.next is not end: 
    current = current.next
    size +=1

  current = head
  for i in xrange(0, size/2):
    current = current.next
  
  return current


def merge(head1, head2):
  if head1 is None: 
    return head2

  if head2 is None: 
    return head1

  head = head1 if head1.data < head2.data else head2
  current = head
  if current is head1: 
    head1 = head1.next
  else:
    head2 = head2.next

  while head1 is not None and head2 is not None: 
    if head1.data < head2.data: 
      current.next = head1
      head1 = head1.next
    else: 
      current.next = head2
      head2 = head2.next

    current = current.next

  if head1 is not None: 
    current.next = head1
  else:
    current.next = head2

  return head


def sort(head, end=None, level=0):
  if head is end:
    return head

  if end is not None:
    end.next = None
  
  mid = get_mid(head, end)
#  print '   '*level, "sorting %s" % (mid.next)
  head2 = sort(mid.next, end, level+1)
  mid.next = None
#  print '   '*level, "sorting %s" % head
  head1 = sort(head, mid, level+1)
  merged = merge(head1, head2)
#  print '   merged ' *level, merged
  return merged

print a1
print sort(a1)