Recursive and iterative approach for mergesort

Problem:


Question 8: *


Mergesort is a type of sorting algorithm. It follows a naturally
recursive procedure:



Break the input list into equally-sized halves Recursively sort both halves Merge the sorted halves. Using your merge function from the
previous question, implement mergesort.



Challenge: Implement mergesort itself iteratively, without using
recursion.

def mergesort(seq):
    """Mergesort algorithm.

    >>> mergesort([4, 2, 5, 2, 1])
    [1, 2, 2, 4, 5]
    >>> mergesort([])     # sorting an empty list
    []
    >>> mergesort([1])   # sorting a one-element list
    [1]
    """
    "*** YOUR CODE HERE ***"

Solution:

```
def merge_iter(lst1, lst2):
"""Merges two sorted lists recursively.

>>> merge_iter([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge_iter([], [2, 4, 6])
[2, 4, 6]
>>> merge_iter([1, 2, 3], [])
[1, 2, 3]
>>> merge_iter([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
"""
new = []
while lst1 and lst2:
if lst1[0] >> merge_recur([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge_recur([], [2, 4, 6])
[2, 4, 6]
>>> merge_recur([1, 2, 3], [])
[1, 2, 3]
>>> merge_recur([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
"""
if not lst1:
return lst2
if not lst2:
return lst1
if lst1[0] > lst2[0]:
return [lst2[0]] + merge_recur(lst1, lst2[1:])
else:
return [lst1[0]] + merge_recur(lst1[1:], lst2)

def mergesort_recur(seq):
"""Mergesort algorithm.

>>> mergesort_recur([4, 2, 5, 2, 1])
[1, 2, 2, 4, 5]
>>> mergesort_recur([]) # sorting an empty list
[]
>>> mergesort_recur([1]) # sorting a one-element list
[1]
"""
if not seq:
return []
if(len(seq) == 1):
return [seq[0]]
middle = len(seq) // 2
left = mergesort_recur(seq[0:middle])
right = mergesort_recur(seq[middle:len(seq)])
return merge_recur(left, right)

def middle(seq):
r

I am not a sorting expert, but I can make a few suggestions based on general Python style:

merge_iter()

-
Rather than getting the 0th element of the two lists, then redefining those lists to drop that element, use pop(0). That removes the element from the list and returns it, like so:

if lst1[0]

Note also that I’m using .append() instead of += because I think it’s slightly clearer, and saves me wrapping the new element in its own list.

-
Rather than new, I’d call the variable sorted_list. That’s a more descriptive term for what that list represents.

merge_recur()

-
You could tidy up the initial check (whether both lists are non-empty) as follows:

if (not lst1) or (not lst2):
return lst1 + lst2


The result is the same, because the empty list has no effect on the sum.

-
I’m nitpicking, but I’d make the final check if lst1[0]

mergesort_recur()

-
Again, you can tidy up the initial check:

if len(seq)

In particular, in the len(seq) == 1 case, there’s no need to take the 0th element, wrap it in a list, and then return it: you can just return seq directly.

-
The variables middle, left and right have similar names, and so could be confused for similar concepts. Actually, they’re two different things: a list index, and two lists.

I’d rename middle to middle_idx to avoid confusion.

-
You’ve defined a function middle(seq), which you could use for getting the value of middle`, and then you don’t use it here. Why?

mergesort_iter()

-
Same comment about tidying up the initial check as in mergesort_recur().

-
I’m confused about why you define a helper() function, then immediately call it within mergesort_iter(). The definition isn’t available outside the function, so all you’ve done is created an extra function call and indented your code a bit further.

Why not take out the function, and dedent the code by one level?

StackExchange Code Review Q#97320, answer score: 4