3
\$\begingroup\$

I just started Stanford Coursera algorithms course and I wrote this mergesort based on what was shown:

def mergesort(n):

    if len(n) <= 1:
        return n

    length = len(n) // 2
    A = mergesort(n[:length])
    B = mergesort(n[length:])
    iterA = 0
    iterB = 0
    C = []
    for i in range(len(n)):
        if A[iterA] <= B[iterB]:
            C.append(A[iterA])
            iterA += 1
        elif B[iterB] <= A[iterA]:
            C.append(B[iterB])
            iterB += 1
        if iterA == len(A):
            C += B[iterB:]
            break
        if iterB == len(B):
            C += A[iterA:]
            break
    return C

It runs decently well but I was wondering what optimizations I could make to it to improve performance? Currently does 1 million numbers in ~8.5 seconds.

\$\endgroup\$
1
  • \$\begingroup\$ Should of fixed it I forgot the equal sign when comparing 2 numbers. \$\endgroup\$
    – Aayush
    Feb 8, 2022 at 1:51

1 Answer 1

1
\$\begingroup\$

Generally, it is a good idea to follow conventions.
For Python, foremost the Style Guide for Python Code.

Write docstrings for all public modules, functions, classes, and methods.

The conventional name for values obtained, but not used is _:
for _ in range(len(items)):
Where there are two alternatives that together cover all possibilities, check for one to handle in the "then-branch", and leave the complement to an else.
You check both lists to have reached their end in each iteration, but only one item has been consumed.

def mergesort(items):
    """ Return a list containing the items in ascending order.
        The result may be items itself.
    """
    n = len(items)
    if n <= 1:  # 2:  # low hanging fruit, then again: this way lies madness
        return items  # if n <=1 or items[0] <= items[1] else [items[1], items[0]]
    # what would be notable performance improvements?
    half = n // 2
    a = mergesort(items[:half])
    last_a = half - 1
    b = mergesort(items[half:])
    last_b = n - half - 1
    i_a = i_b = 0
    c = []
    while True:
        if a[i_a] <= b[i_b]:
            c.append(a[i_a])
            if last_a <= i_a:
                return c + b[i_b:]
            i_a += 1
        else:  # b[i_b] < a[i_a]
            c.append(b[i_b])
            if last_b <= i_b:
                return c + a[i_a:]
            i_b += 1

(While i is perfect for the short-lived index/iteration variable, i_a&i_b look off.)
(note the duplication between a and b not eased by introducing last_a/b.)


I was wondering what optimizations I could make to [my mergesort()] to improve performance?

Glad you took a break there and did not present code difficult to read for all the improvements tried.
Things to do regarding performance:
• Model performance:
 · Input: size, range, distribution, proportion of duplicates
 · Resources: cores, threads, main memory, whatever
• for "microbenchmarks", find a framework rather than trying to roll your own
• before starting to modify the code, have some functional test in place
  (starting with comparing results with "the original")
• measure on different "platforms", if at all possible
• for Python try PyPy or similar


Common starting points for improving mergesort:
• allocate a single "temporary buffer", once
  (advantage to slicing the original/outer input: works for any iterable, not just lists.)
• try to handle runs, starting with exploiting runs in the input
• for "small sets", avoid the setup of mergesort by using a simpler sort
  (Shell sort may be interesting to compare to insertion sort, here.)

\$\endgroup\$
1
  • \$\begingroup\$ One implementation to scrutinise: Kelly Bundy's \$\endgroup\$
    – greybeard
    Feb 10, 2022 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.