Return to Answer

###Step 1:

I would change the computation of mid to:

mid = start + (start - end) // 2

Although python won't give you the wrong answer if you use yours, you theoretically lose performance with lots of elements (>2⁶³).

Also, the code when you are doing the final part of the merge can be simplified to:

if i < len(sub_part1):
 result.extend(sub_part1[i:])
else:
 result.extend(sub_part2[j:])

Which is just cleaner. This can be further improved to:

result.extend(sub_part1[i:])
result.extend(sub_part2[j:])

because the cost of the if statement is more than the cost of appending nothing.

###Step 2:

One of the tricks most implementations of mergesort use is they call a slightly different version of themselves at the beginning who's signature is:

def merge_sort(numbers, start, end, result):
 ...

The advantage of this is that you can alternate which list is your numbers and which list stores the result to avoid allocation or appending to arrays. (because you merge onto an existing result array).

Finally, if you want a fast implementation that feels like cheating (why I love Python), you can use this version from wikibooks.

from heapq import merge
def mergesort(w):
 if len(w)<2:
 return w
 else: 
 mid=len(w)//2
 return merge(mergesort(w[:mid]), mergesort(w[mid:]))

Step 1:

I would change the computation of mid to:

mid = start + (start - end) // 2

Although python won't give you the wrong answer if you use yours, you theoretically lose performance with lots of elements (>2⁶³).

Also, the code when you are doing the final part of the merge can be simplified to:

if i < len(sub_part1):
 result.extend(sub_part1[i:])
else:
 result.extend(sub_part2[j:])

Which is just cleaner. This can be further improved to:

result.extend(sub_part1[i:])
result.extend(sub_part2[j:])

because the cost of the if statement is more than the cost of appending nothing.

Step 2:

One of the tricks most implementations of mergesort use is they call a slightly different version of themselves at the beginning who's signature is:

def merge_sort(numbers, start, end, result):
 ...

The advantage of this is that you can alternate which list is your numbers and which list stores the result to avoid allocation or appending to arrays. (because you merge onto an existing result array).

Finally, if you want a fast implementation that feels like cheating (why I love Python), you can use this version from wikibooks.

from heapq import merge
def mergesort(w):
 if len(w)<2:
 return w
 else: 
 mid=len(w)//2
 return merge(mergesort(w[:mid]), mergesort(w[mid:]))

Step 1:

I would change the computation of mid to mid = start + (start - end) // 2. Although python won't give you the wrong answer if you use yours, you theoretically lose performance with lots of elements (>2^63).

Also the code when you are doing the final part of the merge can be simplified to

if i < len(sub_part1):
 result.extend(sub_part1[i:])
else:
 result.extend(sub_part2[j:])

which is just cleaner. This can be further improved to

result.extend(sub_part1[i:])
result.extend(sub_part2[j:])

because the cost of the if statement is more than the cost of appending nothing.

Step 2:

One of the tricks most implementations of mergesort use is they call a slightly different version of themselves at the beginning who's signature is

def merge_sort(numbers, start, end, result):

The advantage of this is that you can alternate which list is your numbers and which list stores the result to avoid allocation or appending to arrays. (because you merge onto an existing result array).

Finally, if you want a fast implementation that feels like cheating (why I love Python), you can use this version from wikibooks.

from heapq import merge
def mergesort(w):
 if len(w)<2:
 return w
 else: 
 mid=len(w)//2
 return merge(mergesort(w[:mid]), mergesort(w[mid:]))

###Step 1:

I would change the computation of mid to:

mid = start + (start - end) // 2

Although python won't give you the wrong answer if you use yours, you theoretically lose performance with lots of elements (>2⁶³).

Also, the code when you are doing the final part of the merge can be simplified to:

if i < len(sub_part1):
 result.extend(sub_part1[i:])
else:
 result.extend(sub_part2[j:])

Which is just cleaner. This can be further improved to:

result.extend(sub_part1[i:])
result.extend(sub_part2[j:])

because the cost of the if statement is more than the cost of appending nothing.

###Step 2:

One of the tricks most implementations of mergesort use is they call a slightly different version of themselves at the beginning who's signature is:

def merge_sort(numbers, start, end, result):
 ...

The advantage of this is that you can alternate which list is your numbers and which list stores the result to avoid allocation or appending to arrays. (because you merge onto an existing result array).

Finally, if you want a fast implementation that feels like cheating (why I love Python), you can use this version from wikibooks.

from heapq import merge
def mergesort(w):
 if len(w)<2:
 return w
 else: 
 mid=len(w)//2
 return merge(mergesort(w[:mid]), mergesort(w[mid:]))