Skip to content

Instantly share code, notes, and snippets.

@Kwisses

Kwisses/merge_sort.py

Created October 21, 2017 01:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Kwisses/66eee988fb03cd16681499ebd0d13dca to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Kwisses/66eee988fb03cd16681499ebd0d13dca to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Kwisses created this gist Oct 21, 2017.
    66 changes: 66 additions & 0 deletions merge_sort.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,66 @@
    class MergeSort:

    def merge_sort(self, array):

    if len(array) <= 1:
    return array

    midpoint = int(len(array) / 2)

    left = []
    right = []

    for i in range(midpoint):
    left.append(array[i])

    for j in range(midpoint, len(array)):
    right.append(array[j])

    left = self.merge_sort(left)
    right = self.merge_sort(right)

    result = MergeSort.merge(left, right)

    return result

    @staticmethod
    def merge(left, right):

    result = []
    left_pointer = right_pointer = result_pointer = 0

    while left_pointer < len(left) or right_pointer < len(right):

    if left_pointer < len(left) and right_pointer < len(right):

    if left[left_pointer] <= right[right_pointer]:
    result.append(left[left_pointer])
    result_pointer += 1
    left_pointer += 1
    else:
    result.append(right[right_pointer])
    result_pointer += 1
    right_pointer += 1

    elif left_pointer < len(left):
    result.append(left[left_pointer])
    result_pointer += 1
    left_pointer += 1

    elif right_pointer < len(right):
    result.append(right[right_pointer])
    result_pointer += 1
    right_pointer += 1

    return result


    def main():
    array = [5, 4, 3, 2, 1]
    print(array)

    result = MergeSort().merge_sort(array)
    print(result)

    if __name__ == "__main__":
    main()