Recursive and iterative approach for mergesort

Question

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] < lst2[0]:
            new += [lst1[0]]
            lst1 = lst1[1:]
        else:
            new += [lst2[0]]
            lst2 = lst2[1:]
    if lst1:
        return new + lst1
    else:
        return new + lst2

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

    >>> 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):
    return len(seq) // 2

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

    >>> mergesort_iter([4, 2, 5, 2, 1])
    [1, 2, 2, 4, 5]
    >>> mergesort_iter([])     # sorting an empty list
    []
    >>> mergesort_iter([1])   # sorting a one-element list
    [1]
    """
    if not seq:
        return []
    if len(seq) == 1:
        return seq
    def helper():
        partition_boundary_list = []
        partition_copy = seq        
        while len(partition_copy) > 1:
            partition_boundary_list +=   [[     [0, middle(partition_copy), False],     [middle(partition_copy), len(partition_copy), False]     ]]
            partition_copy = partition_copy[0:middle(partition_copy)]
        list_index = len(partition_boundary_list) - 1
        left_memoiz = -1
        right_memoiz = -1       
        while partition_boundary_list:
            partition_boundary_element = partition_boundary_list[list_index]
            left_lower, left_upper, sorted_left = partition_boundary_element[0]
            right_lower, right_upper, sorted_right =  partition_boundary_element[1]
            if left_lower == left_memoiz:          #Using left_memoiz to check, if already sorted
                partition_boundary_list[list_index][0][2] = True
            if right_upper == right_memoiz:        #Using right_memoiz to check, if already sorted
                partition_boundary_list[list_index][1][2] = True

            if left_upper - left_lower > 1 and  (not partition_boundary_list[list_index][0][2]):
                mid = (left_lower + left_upper) // 2
                partition_boundary_list +=  [[    [left_lower, mid, False],     [mid, left_upper, False]    ]]
                list_index += 1 
            elif right_upper - right_lower > 1 and (not partition_boundary_list[list_index][1][2]):  
                mid = (right_lower + right_upper) // 2
                partition_boundary_list += [[     [right_lower, mid, False],     [mid, right_upper, False]     ]]
                list_index += 1         
            else:
                left_memoiz = left_lower
                right_memoiz = right_upper
                ret_seq = merge_iter(seq[left_lower:left_upper], seq[right_lower:right_upper])
                for element in ret_seq:    # copy sorted sequence
                    seq[left_lower] = element
                    left_lower += 1
                partition_boundary_list.pop(list_index)
                list_index -= 1
    helper()
    return  seq

Problem exercise did not ask for in place sort.

Can this code be improved, specifically the iterative version of mergesort as inplace?

Answer 1

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] < lst2[0]:
      new.append(lst1.pop(0))
  else:
      new.append(lst2.pop(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] < lst2[0], just to be consistent with the check in merge_iter(). That’s not a hard rule, I just think that sort of consistency is nice.

mergesort_recur()

• Again, you can tidy up the initial check:

  if len(seq) <= 1:
      return 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?

Answer 2

Sorting algorithms are typically defined to sort their input in-place, and the canonical definition of mergesort is not different. This means that, as a general rule, you don't get to pop or append items from the lists you are merging. Also, in the merging step, rather than doing the merging into an auxiliary list, you copy into auxiliary storage data that could be overwritten, and merge directly into the original list:

def merge(lst, lo, mid, hi):
    """
    Assuming that lst[lo:mid] and lst[mid:hi] are sorted, a call
    to merge will make lst[lo:hi] be sorted, using O(mid - lo)
    auxiliary space.
    """
    assert lo < len(lst) and mid < len(lst) and hi <= len(lst)
    # Copy the data that may be overwritten
    aux = lst[lo:mid]
    # Initialize pointer indices
    read1, read2, write = 0, mid, lo
    while read1 < len(aux) and read2 < hi:
        if lst[read2] < aux[read1]:
            lst[write]= lst[read2]
            read2 += 1
        else:
            lst[write] = aux[read1]
            read1 += 1
        write += 1
    # If there are items left in aux, copy them. Note that any
    # unprocessed item in lst[mid:hi] is already in place
    lst[write:hi] = aux[read1:]

With an in-place merge function like the above, the recursive approach is very simple to code:

def mergesort(lst, lo=0, hi=None):
    if hi is None:
        hi = len(lst)
    if hi - lo > 1:
        mid = lo + (hi - lo) // 2
        mergesort(lst, lo, mid)
        mergesort(lst, mid, hi)
        merge(lst, lo, mid, hi)
    # Nothing to return, sorting is done in-place

Making an iterative mergesort that behaves exactly as the recursive one is a little involved, but if we do things a little differently, it is simple:

def mergesort_iter(lst):
    step = 2
    while step <= len(lst) // 2:
        lo = 0
        mid = lo + step
        while mid < len(lst):
            hi = mid + step
            if hi > len(lst):
                hi = len(lst)
            merge(lst, lo, mid, hi)
            lo = hi
            mid = lo + step
        step *= 2

The only issue with this bottom-up iterative approach is that it may lead to a last very unbalanced merge.

Answer 3

You have a correctness problem and an efficiency problem.

One of the nice properties of mergesort is that it is stable: items that have the same value in the input will appear in the same relative order in the output. This merge is not quite correct because it is not stable. To make it stable, the merge should prefer to take items from lst1 rather than lst2 in case of a tie. That is, you need to change if lst1[0] < lst2[0] to if lst1[0] <= lst2[0].

The merge is inefficient because you keep slicing off the first item of a list. That would require all of the subsequent items to be copied over by one position. That increases your running time from O(n) to O(n²), which is generally considered unacceptably slow.

Answer 4

Whats the effort of:

lst1 = lst1[1:]

in merger_iter()?

So if it is \$O(n)\$ to copy all elements to get rid of the first, (instead \$O(1)\$ to reference and return the first element) your algorithm at least takes \$O(n^2 * log(n))\$ instead of \$O(n*log(n))\$.