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.

Without going into why aren't the methods static, what's the usage of bucket etc.. Where's the code that uses this class? — Egal
– Egal, Commented Sep 9, 2017 at 16:07
@Yigal the bucket is supposed to hold the sorted array. I'm updating the code with calling code. — Melissa Stewart
– Melissa Stewart, Commented Sep 9, 2017 at 16:16
If you are just calling the _sort() method using your class, you don't need to initialize with a bucket variable. — Daniel
– Daniel, Commented Sep 9, 2017 at 16:19
Split the arrays till you've 1 element left - note this could be done in one step by considering an array of n elements as n sub-arrays of 1 element each, then using iteration to update indices and merge those sub-arrays. This would be a "bottom up" merge sort. — rcgldr
– rcgldr, Commented Sep 9, 2017 at 19:02

Daniel · Accepted Answer · 2017-09-09 16:16:18Z

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]

Collectives™ on Stack Overflow

Merge sort implementation in Python using a different approach

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related