merge sort in python

Here's a Python implementation of the merge sort algorithm:

main.py
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:]
    result += right[j:]

    return result
543 chars
31 lines

First, we define a merge_sort function that takes an array as input. This function recursively divides the input array into two halves until each sub-array contains only one element, then merges these sub-arrays to produce the final sorted result.

The merge function is a helper function for merge_sort that takes two sub-arrays and merges them together into a single sorted array. It does this by comparing the first element of each sub-array and adding the smaller one to the result array. Once one of the sub-arrays is fully added to the result array, the remaining elements from the other sub-array are added to the end of the result.

To sort an array using this algorithm, simply call merge_sort with the array as its argument. The sorted array will be returned by the function.