Merge sort python infinite loop

Question

I have decide to learn python recently! I want to write an easy merge sort using the following code :

def mergeSort(lst):
    l = len(lst)

    if l <= 0:
        print("empty")
        return None
    elif l == 1:
        return lst

    half = int(l / 2)
    m = lst[half]

    print(half, m)

    left = []
    right = []

    for n in lst:
        if n < m:
            left.append(n)
        else:
            right.append(n)

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)

Unfortunately this code generates a infinite loop, when it has to deal with a list such as [1 1 1]. Can you suggest some way to fix this wrong behavior?

Answer 1

Have you checked out http://www.geekviewpoint.com/? It's probably the best way to learn how to write algorithms in Python the easy way. Check it out. As a bonus it's a very clean website where the only advertisement I have seen recently is about an android brainy puzzle app by axdlab called "Puzz!". The site itself has all sorts of algorithms and good explanations.

Here is their merge sort:

#=======================================================================
#  Author: Isai Damier
#  Title: Mergesort
#  Project: geekviewpoint
#  Package: algorithm.sorting
#
#  Statement:
#  Given a disordered list of integers (or any other items),
#  rearrange the integers in natural order.
#
#  Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
#
#  Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
#  Time Complexity of Solution:
#  Best = Average = Worst = O(nlog(n)).
#
#  Approach:
#   Merge sort is a divide and conquer algorithm. In the divide and
#   conquer paradigm, a problem is broken into pieces where each piece
#   still retains all the properties of the larger problem -- except
#   its size. To solve the original problem, each piece is solved
#   individually; then the pieces are merged back together.
#
#   For illustration, imagine needing to sort an array of 200 elements
#   using selection sort. Since selection sort takes O(n^2), it would
#   take about 40,000 time units to sort the array. Now imagine
#   splitting the array into ten equal pieces and sorting each piece
#   individually still using selection sort. Now it would take 400
#   time units to sort each piece; for a grand total of 10400 = 4000.
#   Once each piece is sorted, merging them back together would take
#   about 200 time units; for a grand total of 200+4000 = 4,200.
#   Clearly 4,200 is an impressive improvement over 40,000. Now
#   imagine greater. Imagine splitting the original array into
#   groups of two and then sorting them. In the end, it would take about
#   1,000 time units to sort the array. That's how merge sort works.
#
#  NOTE to the Python experts:
#     While it might seem more "Pythonic" to take such approach as
#
#         mid = len(aList) / 2
#         left = mergesort(aList[:mid])
#         right = mergesort(aList[mid:])
#
#     That approach take too much memory for creating sublists.
#=======================================================================
 def mergesort( aList ):
  _mergesort( aList, 0, len( aList ) - 1 )


def _mergesort( aList, first, last ):
  # break problem into smaller structurally identical pieces
  mid = ( first + last ) / 2
  if first < last:
    _mergesort( aList, first, mid )
    _mergesort( aList, mid + 1, last )

  # merge solved pieces to get solution to original problem
  a, f, l = 0, first, mid + 1
  tmp = [None] * ( last - first + 1 )

  while f <= mid and l <= last:
    if aList[f] < aList[l] :
      tmp[a] = aList[f]
      f += 1
    else:
      tmp[a] = aList[l]
      l += 1
    a += 1

  if f <= mid :
    tmp[a:] = aList[f:mid + 1]

  if l <= last:
    tmp[a:] = aList[l:last + 1]

  a = 0
  while first <= last:
    aList[first] = tmp[a]
    first += 1
    a += 1

Here is the testbench:

import unittest
from algorithms import sorting

class Test( unittest.TestCase ):

  def testMergesort( self ):
      A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5]
      sorting.mergesort( A )
      for i in range( 1, len( A ) ):
          if A[i - 1] > A[i]:
            self.fail( "mergesort method fails." )

Answer 2

The algorithm you implemented is (a flawed) quick sort without removing the so-called "pivot" element, in your case m.

The merge operation you do does not need to do any merging as in merge sort, because the a call to mergeSort(left) would already return a sorted left, if you were to handle the pivot correctly.

In merge sort, you don't have a pivot element m, instead, you just halve the list into two parts, as described by James.

As a rule of thumb, recursive calls should always operate on smaller sets of data.

Answer 3

I believe you're just supposed to divide the list in half at the midpoint - not sort which items go into each half.

So instead of this:

   left = []
   right = []
   for n in lst:
       if n < m:
           left.append(n)
       else:
           right.append(n)

just do this:

   left = lst[:half]
   right = lst[half:]