CODEWITHSUNDEEP
pythonpython-3.xrecursionlinked-listmergesort
Yondaru
Yondaru

Reputation: 87

Recursive Merge Sort on linked lists in python

i would like to ask you for help with this project i am working on where i have to write recursive merge sort function that will work on linked lists.this is what i have so far(i didnt put whole code here just the part i am struggling with).

    ....
    def merge_sort(self):
        len_list,len_list2= 0, 0
        list=self.head         #first half of linked list
        list2=self.divide()    #function that makes second half of linked list        
        #from imput like z = SortedList([46, 27, 93, 91, 23])
        #i will get list=46->27->93->None
        #           list2=91->23->
        while list is not None:
            len_list+=1
            list=list.next
        while list2 is not None:
            len_list2+=1
            list2=list2.next
        # in len_list,len_list2 i am storing length of these linked lists

        def merge(self,left,right):
            result,i,j=None,0,0
            while (i<len_list) and (j<len_list2):
                if list.data < list2.data:
                    result.append(list.data)  #append is function which appends   
                    list=list.next            #nodes            
                    i+=1
                else:
                    result.append(list2.data)
                    list2=list2.next
                    j+=1
               #some returns should follow but i dont know what to do

I am pretty sure this is wrong on many levels I was just trying to copy Merge sort function for Lists and convert it on Linked lists. If anyone can help me how to do this, without changing arguments of definitions as( def merge_sort(self)) and show me how to recursively call it, I would appreciate it a lot. Thank you beforehand. Also for making linked lists in halfs i should use function divide(self) but if you know any other way let me know

Upvotes: 3

Views: 2106

Answers (1)

Tom Kealy
Tom Kealy

Reputation: 2669

Generally list.head is implemented so that it will return a reference to the first element of your list, and not the first half of the list. Maybe it would be better to implement list.divide() to return tow lists:

left_half, right_half = self.divide()

Even better, and maybe more pythonic, would be in your LinkedList class, implement the methods __getitem__ and __len__.

Something like:

def __len__(self):
    return len(self.list)

def __getitem__(self, position):
    return self.list(position)

The first allows you to get the length quickly, the second will allow you to slice items.

The basic structure of merge sort is:

def merge_sort(list):
    #Check the list doesn't have 1 item
    if len(list) == 1:
       return list
    #Find the middle of the list
    middle = len(list)//2

    #Find the left and right halfs via slicing
    left = list(:middle)
    right = list(middle:)

    #Recursively sort your lists
    left = merge_sort(left)
    right = merge_sort(right)

    #Merge them together  
    return LinkedList(merge(left, right)

Upvotes: 1

Related Questions