Python3 - merge sort, O(n) space efficiency

Question

Any critique of my implementation of Merge sort would be much appreciated! I tested it using a driver function (shown below), and everything works. However, it still feels unwieldy, I am a beginner so I really want to hear any criticisms, constructive or not :)

def inplace_merge_sort( lst, start = 0 , end = None ):
  def inplace_merge( lst1_start, lst1_end , lst2_start, lst2_end ): #needs to take in two sets of unsorted indices 
    start, end = lst1_start, lst2_end
    for _ in range( (end - start) ):
      if(lst[lst1_start] < lst[lst2_start]):
        lst1_start += 1

      else:
        lst.insert(lst1_start , lst[lst2_start])
        del lst[lst2_start + 1]
        lst1_start += 1
        lst2_start += 1

      if( lst1_start == lst2_start or lst2_start == lst2_end):
        break

    return start, end #returns indices of sorted newly sublist



  if( len(lst) == 1 or len(lst) == 0): #catches edge cases
    return lst

  if end is None: end = len(lst) #so I don't have to input parameters on first call 

  
  length_sublist = end - start 

  if( length_sublist > 1):
    start1, end1 = inplace_merge_sort( lst, start, (end + start) // 2  )
    start2, end2 = inplace_merge_sort( lst, (end + start) // 2 , end  )
  
    return inplace_merge(start1, end1, start2, end2)

  else: 
    return start, end

Here is the test function

def inplace_driver_helper(f_n):
  def modified_list_returner( lst ):
    f_n(lst)
    return lst
  return modified_list_returner

def driver(f_n):
  # NICK I added these two test cases to catch some popular edge cases.
    assert f_n([]) == []
    assert f_n([4]) == [4]

    assert f_n([1,2,3]) == [1,2,3]

    assert f_n([3,2,1]) == [1,2,3]

    assert f_n([1,2,3,1,2,3]) == [1,1,2,2,3,3]

    assert f_n([1,2,3,1,1,2,3]) == [1,1,1,2,2,3,3]

    assert f_n([-1,0,46,2,3,1,2,3]) == [-1,0,1,2,2,3,3,46]

and when we run this,

if __name__ == '__main__':
    driver(inplace_driver_helper(inplace_merge_sort))

    print('done')

The output is 'done'!

Answer 1

• Merge is usually O(m) time, where m is the number of elements involved in the merge. Due to your insertions and deletions, it's rather O(mn), where n is the length of the entire list. That makes your whole sort O(n^2 log n) time instead of mergesort's usual O(n log n).
• You call it inplace sort, which suggests it doesn't return anything, but you do return the list if it's short and you return some start/end indices otherwise. Rather inconsistent and confusing. I'd make it not return anything (other than the default None).
• Your function offers to sort only a part of the list, but you don't test that.
• You use quite a few rather long variable names. I'd use shorter ones, especially i and j for the main running indices.
• You insert before you delete. This might require the entire list to be reallocated and take O(n) extra space if it doesn't have an extra spot overallocated. Deleting (or popping) before inserting reduces that risk and thus increases the chance that you only take O(log n) extra space.
• Mergesort ought to be stable. Yours isn't, as in case of a tie, your merge prefers the right half's next value. For example, you turn [0, 0.0] into [0.0, 0].

A modified version:

def inplace_merge_sort(lst, start=0, stop=None):
    """Sort lst[start:stop]."""

    def merge(i, j, stop):
        """Merge lst[i:j] and lst[j:stop]."""
        while i < j < stop:
            if lst[j] < lst[i]:
                lst.insert(i, lst.pop(j))
                j += 1
            i += 1

    if stop is None:
        stop = len(lst)

    middle = (start + stop) // 2
    if middle > start:
        inplace_merge_sort(lst, start, middle)
        inplace_merge_sort(lst, middle, stop)
        merge(start, middle, stop)

Oh, I renamed end to stop, as that's what Python mostly uses, for example:

>>> help(slice)
Help on class slice in module builtins:

class slice(object)
 |  slice(stop)
 |  slice(start, stop[, step])

>>> help(list.index)
Help on method_descriptor:

index(self, value, start=0, stop=9223372036854775807, /)

>>> help(range)
Help on class range in module builtins:

class range(object)
 |  range(stop) -> range object
 |  range(start, stop[, step]) -> range object
```

Answer 2

Welcome to Code Review!

PEP-8

Python has a style guide to help developers write clean, maintainable and readable code. It is referred to as PEP-8. A few points of note:

1. Avoid extraneous whitespace in the following situations:
2. Use 4 spaces per indentation level.

Type hinting

Yet another PEP (PEP-484) for putting in type hints for your variables and function parameters.

Comments

Except for the comment in testing driver about corner cases, all other comments are actually not needed. The code explains what the comments are trying to say anyway.

Loop over range

You have a loop with range:

for _ in range( (end - start) ):

where you actually make use of lst1_start. Why not start iterating from this index itself?

Names

The variable names: length_sublist, lst1_start/end and similarly lst2_start/end are more readable (and sensible) as sublist_length, start1/end1, start2/end2. Since you do not have 2 different lists anywhere, lst1/2 are more confusing.

Testing

The driver for your test environment requires its own wrapper, which the testing suite needs to incorporate. This feels wrong, and should be handled by the test driver itself. Also, python provides an excellent testing module, unittest. For the driver:

@inplace_driver_helper
def driver(f_n):
    # rest of your code

is enough.

Answer 3

• You define inplace_merge() inside the definition of inplace_merge_sort(), but it doesn't use any of the context of inplace_merge_sort(), so it isn't necessary.

  If you defined it outside of the definition (perhaps with a leading underscore in the identifier to warn clients it was not meant to be used directly), you would get three advantages:

  • The definition would only be executed once on import, and not on every call.
  • It could be tested directly.
  • The start and end identifiers wouldn't hide other identifiers of the same name, and risk confusing a reader about which they referred to.

• If you replaced:

   if( len(lst) == 1 or len(lst) == 0): #catches edge cases
  

  with

   if len(lst) <= 1:
  

then the length wouldn't need to be calculated twice (which, to be fair, is probably not a slow operation).

• I agree with other answers that there should be no return value, but if there is, you should be testing it. (In fact, I would test that it always returns None.)