Python3 - merge sort, O(n) space efficiency

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'!

• 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
$$$$

• Thank you, this is so much cleaner! To confirm my understanding, your new function fixes the return issue (bullet two) because now if the length of the sub-list is <1 the function just does nothing. Also a second question I had regarding bullet one, would your new function still be O(mn) because insert and pop operations are linear? Would a way around this be to use a Linked List or something? Oct 19, 2020 at 15:19
• @JosephGutstadt Yes, as I don't have an explicit return ..., it only returns the default None. Not the list and not the start/end. Yes, the complexity is still the same, as I kept your insert/delete way (it's the only thing that makes it different from normal implementations, and thus the only thing that makes it interesting :-). And if the data is given as a linked list, then yes, you can merge with O(m) time and O(1) space. Of course if you're given a list and then convert it to some linked list, that extra linked list then costs O(n) space. Oct 19, 2020 at 15:29
• Nice that makes sense, but wait if it was a LinkedList wouldn't the List accesors inside of the merge function take extra time? Sorry just trying to figure out how inplace merge could be O(log(n)*n) in time, since regular merge is Oct 19, 2020 at 15:48
• @JosephGutstadt What do you mean with list accessors? Like lst[i]? That would cost extra time, yes. Which is why you wouldn't do that :-). You'd work with references to the current list nodes, so accessing their values is O(1). Oct 19, 2020 at 15:53
• yes that was what I was talking about :). I think that makes sense, so at a high level we would replace the start, middle, and stop indices with actual pointers to parts in the LL? Oct 19, 2020 at 15:56

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.

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):


is enough.

• 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.)
• What do you mean with "doesn't use any of the context"? It does use lst. Very good points, though. Oct 19, 2020 at 10:53
• @superbrain: squints Oh dear. You are absolutely right. Sorry to the OP. I would still recommend moving it out, but a speed test might be worthwhile to see if the extra parameter requited makes it take longer. Oct 19, 2020 at 11:21
• I do see a significant speed difference in a pure test, but I suspect in the real code with the high merge costs, it'll be invisible. But might make a slight noticeable difference with a normal merge. Oct 19, 2020 at 11:30
• @superbrain: That timing test supports my naive recommendation to move the function out (presumably because of the reason I cited: "The definition would only be executed once on import, and not on every call.") But based on your observation that lst is used in the function, an additional lst` parameter would need to be added to the function, and that may have a greater impact (because it is frequently called) that outweighs the small benefit. [A timing test confirmed at about 10-20 calls, the cost of the param outweighs the cost of the definition.] Oct 19, 2020 at 12:08
• Right, a test with a list is more relevant. The nested function seems to suffer more from that, though. Oct 19, 2020 at 12:31