Merge Sort in Python

Merge sort is an algorithm for sorting an array by dividing it in half, sorting each half, and then merging the sorted halves back together. It works by recursively dividing the array in half until each sub-array contains only one element, and then merging the sub-arrays back together in a sorted order.

Here is an example of how you might implement merge sort in Python:

def merge_sort(array):

    if len(array) <= 1:

        return array

    mid = len(array) // 2

    left = array[:mid]

    right = array[mid:]

    left = merge_sort(left)

    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):

    merged = []

    while left and right:

        if left[0] < right[0]:

            merged.append(left.pop(0))

        else:

            merged.append(right.pop(0))

    merged.extend(left)

    merged.extend(right)

    return merged

array = [4, 3, 2, 1]

sorted_array = merge_sort(array)

print(sorted_array) # Outputs [1, 2, 3, 4]

In this example, the merge_sort function takes an array as input and returns the sorted array. If the array contains only one element, it is already sorted and is returned as is. Otherwise, it divides the array in half, calls itself recursively on each half, and then calls the merge function to merge the sorted halves back together. The merge function takes two sorted arrays as input and returns a single sorted array by iterating through both arrays and adding the smaller element to the merged array until one of the arrays is empty.