Merge Sort in Python

sammyGH
by sammyGH · 3 posts
4 years ago in Python
Posted 4 years ago · Author
I found some good code explaning Merge sort online and thought you guys might wanna take a look at it expecially if youre new to programming and/or python.
Code
def merge(left, right):
    # If the first array is empty, then nothing needs
    # to be merged, and you can return the second array as the result
    if(left and right):
        print('Left: ')
        print(left)
        print('Right: ')
        print(right)

    if len(left) == 0:
        return right
    # If the second array is empty, then nothing needs
    # to be merged, and you can return the first array as the result
    if len(right) == 0:
        return left

    result = []
    index_left = index_right = 0
    # Now go through both arrays until all the elements
    # make it into the resultant array
    while len(result) < len(left) + len(right):  # sorts/combines both sides
        # The elements need to be sorted to add them to the
        # resultant array, so you need to decide whether to get
        # the next element from the first or the second array
        if left[index_left] <= right[index_right]:
            result.append(left[index_left])
            index_left += 1
        else:
            result.append(right[index_right])
            index_right += 1

        # If you reach the end of either array, then you can
        # add the remaining elements from the other array to
        # the result and break the loop
        if index_right == len(right):
            result += left[index_left:]
            break
        if index_left == len(left):
            result += right[index_right:]
            break
    print('result:')
    print(result)
    return result


def merge_sort(list):
    # If the input array contains fewer than two elements,
    # then return it as the result of the function
    print(list)
    if len(list) < 2:
        return list
    midpoint = len(list) // 2
    # Sort the array by recursively splitting the input
    # into two equal halves, sorting each half and merging them
    # together into the final result
    return merge(
        left=merge_sort(list[:midpoint]),
        right=merge_sort(list[midpoint:]))


-- Sun Nov 22, 2020 9:52 pm --

Heres quick sort!
from random import randint


def quick_sort(arr):
# If the input array contains fewer than two elements,
# then return it as the result of the function
if len(arr) < 2:
return arr

low, same, high = [], [], []

pivot = arr[randint(0, len(arr) - 1)] # Select your `pivot` element randomly

for item in arr:
# Elements that are smaller than the `pivot` go to
# the `low` list. Elements that are larger than
# `pivot` go to the `high` list. Elements that are
# equal to `pivot` go to the `same` list.
if item < pivot:
low.append(item)

elif item == pivot:
same.append(item)

elif item > pivot:
high.append(item)
# The final result combines the sorted `low` list
# with the `same` list and the sorted `high` list
return quick_sort(low) + same + quick_sort(high)
Posted 4 years ago
these programming things are so confusing i gotta learn it
Posted 4 years ago
@drxdior


If you want a good resource on sorting algorithms, I recommend purchasing a book on "Data Structures and Algorithm Analysis". Here is the one I use: https://www.amazon.com/Data-Structures- ... 08&sr=8-16

Create an account or sign in to comment

You need to be a member in order to leave a comment

Sign in

Already have an account? Sign in here

SIGN IN NOW

Create an account

Sign up for a new account in our community. It's easy!

REGISTER A NEW ACCOUNT