def MargeSort(head):

     if head == None or head.getNext() == None:
        return head

     midnode=middleNode(head)
     secondhalf=midnode.getNext()
     midnode.setNext(None)

     return  marge(MargeSort(head),MargeSort(secondhalf))

def marge(firsthalf,secondhalf):
    news=Node()
   # prst=news
    news.setData(firsthalf.getData())
    while firsthalf!=None:
        print "first half",firsthalf.getData()
        news.setNext(firsthalf)
        firsthalf=firsthalf.getNext()
    while secondhalf!=None:
        print "second half", secondhalf.getData()
        news.setNext(secondhalf)
        secondhalf=secondhalf.getNext()
    print "------------------------MERGED-------------------------"
    #current=Node()
    #sort=current
#    #print sort.getNext()
    #while firsthalf !=None and  secondhalf!=None:
     #   if firsthalf.getData() < secondhalf.getData():
      #      current.setNext(firsthalf)
       #     firsthalf=firsthalf.getNext()
       # else:
        #    current.setNext(secondhalf)
         #   secondhalf=secondhalf.getNext()
    #if firsthalf==None:
     #   while secondhalf!=None:
      #      current.setNext(secondhalf)
       #     secondhalf=secondhalf.getNext()

#    else:
       # while firsthalf!=None:
        #    current.setNext(firsthalf)
         #   firsthalf=firsthalf.getNext()
    return news

def middleNode(node):
    if node==None:
        return node
    mid=node
    end=node
    while end.getNext()!=None and mid.getNext()!=None and (end.getNext()).getNext()!=None:
        mid=mid.getNext()
        end=(end.getNext()).getNext()

    return mid

----------------------------------------------
    first half 9
    second half 5
    ------------------------MERGED-------------------------
    first half 9
    first half 5
    second half 6
    ------------------------MERGED-------------------------
    first half 7
    second half -9
    ------------------------MERGED-------------------------
    first half 7
    first half -9
    second half 10
    ------------------------MERGED-------------------------
    first half 9
    first half 6
    second half 7
    second half 10
    ------------------------MERGED-------------------------

    Process finished with exit code 0