Merge sort implementation in Python using a different approach

Question

There are numerous implementations of merge sort I've seen, however, I'm trying to write one which translates literally from the algorithmic definition of merge sort:

• Split the arrays till you've 1 element left
• Merge them together.

However I'm a little stuck. This is my code till now,

class MergeSort:
    def __init__(self):
        bucket = []

    def _sort(self, arr):
        if len(arr) == 1:
            pass

        mid = len(arr) //2
        self._sort(arr[:mid])
        self._sort(arr[mid:])

    def _merge(self, arr1, arr2, arr):
        i, j = 0, 0
        while i < len(arr1) and j < len(arr2):
            if arr1[i] < arr2[j]:
                arr.append(arr1[i])
                i += 1
            else:
                arr.append(arr2[j])
                j += 1

The code will be called in this manner.

merge_sort = MergeSort()
merge_sort._sort([1,9,3,2,5])

Can someone help me stitch these two methods together to get the merge sort someway. Just to reiterate I'm not looking at a new approach. Thanks.

Answer 1

I'm not 100% clear why you need to encapsulate your logic within a class (this decision leads down a rabbit hole of questions re.: Python idioms of class design, etc.). The below code, though, implements merge sort in Python as defined by the algorithm:

class MergeSort:

    def _sort(self, arr):
        arr1 = []
        arr2 = []

        n = len(arr)

        if n <= 1:
            return

        for i in range(0, n):
            if i < (n / 2):
                arr1.append(arr[i])
            else:
                arr2.append(arr[i])

        self._sort(arr1)
        self._sort(arr2)
        self._merge(arr, arr1, arr2)
        return arr

    def _merge(self, arr, arr1, arr2):  
        end1 = len(arr1)
        end2 = len(arr2)
        start1 = 0
        start2 = 0
        k = 0

        while (start1 < end1) and (start2 < end2):
            if arr1[start1] < arr2[start2]:
                arr[k] = arr1[start1]
                start1 += 1
            else:
                arr[k] = arr2[start2]
                start2 += 1
            k += 1

        while start1 < end1:
            arr[k] = arr1[start1]
            start1 += 1
            k += 1

        while start2 < end2:
            arr[k] = arr2[start2]
            start2 += 1
            k += 1

Which yields:

>>>lis = [4,1,6,2,3,8,9,7]
>>>print "Sorted array: ", MergeSort()._sort(lis)
Sorted array:  [1, 2, 3, 4, 6, 7, 8, 9]