Merge Sort implementation with generators and recursion

Question

Just beating the dead merge-sort horse, this time with generators and recursion!

What do you think?

p.s. Not entirely sure why stack overflow needs me to post more details on a code review. I'm implementing something straight from an undergrad CS class but because it does, here Is the video that inspired me https://www.youtube.com/watch?v=TzeBrDU-JaY

k=[1,2,1,3,4,2]
def merge_sort(lis):
    """this performs merge sort assuming
none of the values in lis are greater than 10**100"""
    if len(lis)<=1:
        return lis
    else:
        over=int(len(lis)/2)
        RL=lis_generator(merge_sort(lis[over:]))
        LL=lis_generator(merge_sort(lis[:over]))
        new_l=list()
        cRL=next(RL)
        cLL=next(LL)
        while len(new_l)<len(lis):
            if cRL<=cLL:
                new_l.append(cRL)
                cRL=next(RL)
            else:
                new_l.append(cLL)
                cLL=next(LL)

        return new_l

def lis_generator(lis):
    """enumerate --> index, value"""
    for i in lis:
        yield i
    yield 10**100

alecxe · Accepted Answer · 2017-08-21 21:09:02Z

You don't actually get benefits from using generators in this particular implementation since you are still slicing actual lists having the slices created in memory. And, you also collect the results into a new_l list being created in memory and returned all at once.

You should use iterative islice() like demonstrated in this example. Also, check out this generator-based merge sort implementation - note how the results are yielded from the "merge sort" function.

Some code style related notes:

since you return from the function when len(lis) <= 1, you can omit the else: part and decrease the indentation level of the case when len(lis) is more than 1
improve your variable naming - lis is not a good way to workaround not naming a variable list, over should probably be middle, cRL and cLL should probably become left and right etc.
documentation strings should start with a capital letter and end with a dot, according to PEP8 style guide (reference)
watch for other PEP8 code style violations - specifically, watch for spaces around operators (reference)

Stack Exchange Network

Merge Sort implementation with generators and recursion

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Merge Sort implementation with generators and recursion

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions