Skip to main content
3 of 3
added 22 characters in body
a3r
  • 41
  • 2

Besides the optimisations which others have already suggested, you could also optimise your code by going beyond the standard merge sort algorithm.

A simple way to make your merge sort a bit more time-efficient is to turn it into a hybrid sorting algorithm, for example. For very small lists, the recursive function calls performed by merge sort can cause some unnecessary overhead. Some other non-recursive sorting algorithms, such as insertion sort, can be faster than merge sort on very small lists.

To implement a simple hybrid sorting algorithm based on merge sort, you can fix a threshold t for the length of the input list. If the length of the list is above the threshold t, you perform the standard split, recursive call, and merge as with merge sort, and if the length of the list is below the threshold, you just sort the list directly, using insertion sort. You might have to play around with different values for the threshold in order to get a function which performs better than the standard merge sort.

You could then also try implementing Timsort, a slightly more sophisticated hybrid algorithm which combines elements of merge sort and insertion sort, and which is used in the built-in sorted method in Python. Your implementation will likely not be as fast as the built-in implementation, but should still be faster than standard mergesort.

a3r
  • 41
  • 2