Merge Sort

 Merge Sort

Merge sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into halves, sorting each half, and merging the two halves back together.

python

# Merge sort function

def merge_sort(arr):

    if len(arr) <= 1:

        return arr

    mid = len(arr) // 2

    left = merge_sort(arr[:mid])

    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):

    result = []

    i, j = 0, 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