Making MergeSort More Efficient

Question

I am working on a hackerrank problem: https://www.hackerrank.com/challenges/big-sorting

And have written an implementation of MergeSort in Python. The algorithm works fine, but I get time-out errors on some of the larger input tests. As I'm not a Python expert, can anybody advise how I can make my code more efficient?

unsorted = map(int, unsorted) # Unsorted is provided as an input, an array of strings


def mergeSort(list):
    s = len(list)

    if s == 1:
        return list

    if s == 2:
        if list[0] < list[1]:
            return list
        return [list[1], list[0]]

    listA = mergeSort(list[:s / 2])
    listB = mergeSort(list[s / 2:])

    r = []

    while len(listA) > 0 or len(listB) > 0:
        if len(listA) == 0:
            r = r + listB
            return r

        if len(listB) == 0:
            r = r + listA
            return r

        if listA[0] < listB[0]:
            r.append(listA.pop(0))
        else:
            r.append(listB.pop(0))


list = mergeSort(unsorted)
for n in list:
    print n

I wouldn't be surprised if mergesort is the wrong algorithm entirely. I haven't looked at the challenge but maybe it's about `O(1)` sortings like radixsort or bucketsort. Did you try the builtin `sorted`? If that also times out you won't beat it with a pure Python `mergesort`. — MSeifert, Aug 30 '17 at 12:58
@MSeifert - the challenge is to sort strings up to a length of 10^6 characters, so radix sort would not be an optimal choice. — rcgldr, Aug 30 '17 at 15:15

score 1 · Answer 1 · answered Aug 30 '17 at 13:30

Running your script against a list of 100000 random numbers between 1 and 10000 gives me this profiling:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    3.687    3.687 <string>:1(<module>)
 131071/1    1.457    0.000    3.687    3.687 \Test\untitled4.py:8(mergeSort)
  1502009    1.903    0.000    1.903    0.000 {method 'pop' of 'list' objects}
  4833703    0.217    0.000    0.217    0.000 {len}
  1502009    0.110    0.000    0.110    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

From it you see that most of the time is spend on the pop() and len() and function calls. The pop(0) could be eliminated by using a lower pointer for example. There are many questions about similar optimizations of mergesort algorithms in python, so please try to apply the optimizations described in the answers under similar questions.

unsurprisingly, pop(0) is the main culprit! – Reblochon Masque Aug 30 '17 at 14:14 — Reblochon Masque, Aug 30 '17 at 14:14

score 0 · Answer 2 · answered Aug 30 '17 at 13:31

The fact that you keep copying the sub-lists by slicing (e.g. list[:s / 2]) uses much more memory than you would if you implemented merge-sort to run "in-place".
It could be that merge sort is too slow, there are algorithms that, with some restrictions, will run much faster such as counting sort and radix sort

rcgldr · Answer 3 · 2017-08-31T03:37:49.060

Someone else has done a similar challenge:

Recursive algorithm works without return statement? (Runs really fast)

For this challenge, the strings have no leading zeroes and are to be treated as integers. A longer string is greater than a shorter string. A length compare needs to be done first and only if the lengths are equal should the strings be compared.

This could be further improved by by doing a one time allocation of an auxiliary array, aux = [none]*n, where n is the number of lines (main() would need to count lines and pass n as a parameter to the sort function). If using a top down merge sort, a pair of mutually recursive functions can be used to avoid copying of data (in this case, I assume the "data" is actually the equivalent of an array of pointers to strings, and that the strings are never moved by the sort). One function ends up with a sorted sub-array in the original array, the other function ends up with a sorted sub-array in the auxiliary array. Each function calls the other one twice, once for left half, once for right half, then merges the two halves. In the special case where the sorted data is to end up in the auxiliary array and a size of 1, a single element is copied from the original to the auxiliary array.

A bottom up merge sort would be a bit faster as it skips all of the recursion used to generate n-1 pairs of indices, and starts off by treating an array of n elements as n sub-arrays of 1 element each, then using iteration to manipulate the indices. It's not a lot faster because most of the time is spent in the merge function and the merge function is identical for both top down and bottom up merge sort. Similar to the optimized top down merge sort, copying is avoided by changing the direction of merge based on the merge pass. The number of merge passes is determined in advance based on n, and if it would be an odd number of passes, the first pass can swap pairs of elements in place, leaving an even number of merge passes to do so the sorted data ends up in the original array.

It appears that this challenge was intended to be implemented in C, since it provides a C snippet. A python implementation will be significantly slower.

Making MergeSort More Efficient

3 Answers3