2

I'm learning merge sort and many tutorials I've seen merge by replacing values of the original array, like the way here. I was wondering if my alternative implementation is correct. I have only seen 1 tutorial do the same. My implementation returns the sorted array which goes like this:

def mergesort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]

    return merge(mergesort(left_arr), mergesort(right_arr))

def merge(left_arr, right_arr):
    merged_arr = [] # put merge of left_arr & right_arr here
    i,j = 0, 0 # indices for left_arr & right_arr

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            merged_arr.append(left_arr[i])
            i += 1
        else:
            merged_arr.append(right_arr[j])
            j += 1

    # add remaining elements to resulting arrray
    merged_arr.extend(left_arr[i:]) 
    merged_arr.extend(right_arr[j:])
    return merged_arr


arr = [12, 11, 13, 5, 6, 7]
sorted_arr = mergesort(arr)
print(sorted_arr)
# Output: [5, 6, 7, 11, 12, 13]

To me, this is a more intuitive way of doing merge sort. Did this implementation break what merge sort should be? Is it less efficient speed-wise or space-wise (Aside from creating the results array)?

Donovan Keating
  • 1,715
  • 3
  • 17
  • 27

4 Answers4

2

If we are considering a merge sort with O(n) extra memory, then your implementation seems to be correct but inefficient. Let's take a look at these lines:

def mergesort(arr):
    ...
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]

You are actually creating two new arrays on each call to mergesort() and then copy elements from the original arr. It's two extra memory allocations on the heap and O(n) copies. Usually, heap memory allocations are quite slow due to complicated allocators algorithms.

Going father, let's consider this line:

merged_arr.append(left_arr[i])  # or similar merged_arr.append(left_arr[j])

Here again a bunch of memory allocations happens because you use a dynamically allocated array (aka list).

So, the most efficient way to mergesort would be to allocate one extra array of size of the original array once at the very beginning and then use its parts for temporary results.

def mergesort(arr):
    mergesort_helper(arr[:], arr, 0, len(arr))

def mergesort_helper(arr, aux, l, r):
    """ sorts from arr to aux """
    if l >= r - 1:
        return

    m = l + (r - l) // 2
    mergesort_helper(aux, arr, l, m)
    mergesort_helper(aux, arr, m, r)
    merge(arr, aux, l, m, r)

def merge(arr, aux, l, m, r):
    i = l
    j = m
    k = l
    while i < m and j < r:
        if arr[i] < arr[j]:
            aux[k] = arr[i]
            i += 1
        else:
            aux[k] = arr[j]
            j += 1
        k += 1

    while i < m:
        aux[k] = arr[i]
        i += 1
        k += 1

    while j < r:
        aux[k] = arr[j]
        j += 1
        k += 1

import random

def testit():
    for _ in range(1000):
        n = random.randint(1, 1000)
        arr = [0]*n
        for i in range(n):
            arr[i] = random.randint(0, 100)

        sarr = sorted(arr)
        mergesort(arr)
        assert sarr == arr

testit()
Ivan Velichko
  • 6,348
  • 6
  • 44
  • 90
  • Merge sorts use O(n) space usually right? So you're saying this alternative version is still technically O(n) but way less efficient? Can you point me to a tutorial that does "allocate one extra array of size of the original array once at the very beginning and then use its parts for temporary results."? – Donovan Keating Oct 31 '18 at 09:08
  • Merge sort also can be implemented in place without using extra memory, check this https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm. – Ivan Velichko Oct 31 '18 at 09:11
  • @DonovanKeating please check the updated answer, I added an example with an aux array. – Ivan Velichko Oct 31 '18 at 10:14
  • 1
    @IvanVelichko Whereas you can implement merge sort with constant extra memory, doing so is not especially efficient. As `n` grows, the amount of time you spend swapping things in and out of the fixed-size auxiliary array begins to dominate the running time. – Jim Mischel Oct 31 '18 at 13:55
  • @JimMischel I adjusted my code, now it doesn't have this extra copy-loop. However, this trick requires the hacky switch between the primary and auxiliary arrays in the sort entry point. – Ivan Velichko Oct 31 '18 at 14:16
  • @IvanVelichko I'm not sure what prompted that, but I agree that the buffer swap is a bit of a hack. You have a good answer here. My comment was in response to your assertion that you can implement merge sort in place. – Jim Mischel Oct 31 '18 at 18:55
1

Do Python guys bother about effectiveness with their lists :) ?

To achieve the best speed of classical merge sort implementation, in compiled languages one should provide auxiliary memory piece only once to minimize allocation operations (memory throughput frequently is limiting stage when arithmetics is rather simple).

Perhaps this approach (preallocation of working space as list with size = source size) might be useful in Python implementation too.

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Are you suggesting in-place merge sort? – Donovan Keating Oct 31 '18 at 09:16
  • No. In-place merge sort is slower, it is interesting mainly theoretically. But providing instant space for algortihm work is common technique. Perhaps you won't get significant gain with Python, but it might be checked. – MBo Oct 31 '18 at 09:22
1

Your implementation of merge sort is right.

As you pointed you are using an extra array to merge your results. Using this alternative array, adds a space complexity of O(n).

However, the first link you mentioned: https://www.geeksforgeeks.org/merge-sort/ also adds the same space complexity:

/* create temp arrays */
int L[n1], R[n2];

Note: In case you are interested, take a look to "in place" merge sort

Ignasi
  • 5,887
  • 7
  • 45
  • 81
1

I think this is a good implementation of merge sort because evaluating the complexity of your algorithm is part of the complexity of the merge sort that is: given n the number of elements to be ordered, 

T(n) = 2T (n / 2) + n
Prima Alessandro
  • 160
  • 7