Merge Sort Implementation in Python

Merge sort is a divide and conquer algorithm that works by splitting an array into smaller sub-arrays, sorting them recursively, and merging the sorted sub-arrays to produce the final sorted array. Merge sort has a time complexity of O(n log n) and a space complexity of O(n).

How Merge Sort Works

The merge sort algorithm works as follows:

1. Divide the unsorted array into n sub-arrays, each containing one element (base case).
2. Repeatedly merge adjacent sub-arrays to produce new sorted sub-arrays until there is only one sub-array remaining, which is the sorted array.

The merge step works as follows:

1. Take two adjacent sub-arrays and compare the first elements of each sub-array.
2. Take the smaller of the two first elements and append it to a new sub-array.
3. Repeat step 2 until one of the sub-arrays is empty.
4. Append the remaining elements of the non-empty sub-array to the new sub-array.
5. The new sub-array is now a sorted sub-array.
6. Repeat steps 1-5 with the new sorted sub-arrays until there is only one sub-array remaining, which is the sorted array.

Merge Sort Implementation

Here is a Python implementation of the merge sort algorithm:

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
    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

The merge_sort function takes an array as an argument and recursively divides the array into two sub-arrays until the base case is reached, which is when the array has one or fewer elements. The merge function takes two sorted sub-arrays as arguments and merges them into a new sorted sub-array.

Here is an example of using the merge_sort function:

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)

The output of this code will be:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Time and Space Complexity

The time complexity of merge sort is O(n log n) in the worst, average, and best cases, making it one of the most efficient sorting algorithms. The space complexity of merge sort is O(n) because it requires temporary storage for the merge step.

Bottom-up Merge Sort Implementation

A bottom-up implementation of merge sort is a non-recursive version that uses an iterative approach to sort the array. It works by dividing the array into sub-arrays of size 1, then merging adjacent sub-arrays to produce new sorted sub-arrays of size 2. This process is repeated with sub-arrays of increasing size until the whole array is sorted.

Here is a Python implementation of the bottom-up merge sort algorithm:

def bottom_up_merge_sort(arr):
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left = arr[i:i+width]
            right = arr[i+width:i+2*width]
            arr[i:i+2*width] = merge(left, right)
        width *= 2
    return arr

The bottom_up_merge_sort function takes an array as an argument and iteratively divides and merges the sub-arrays until the whole array is sorted. The merge function is the same as in the recursive implementation.

Here is an example of using the bottom_up_merge_sort function:

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = bottom_up_merge_sort(arr)
print(sorted_arr)

The output of this code will be:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Time and Space Complexity

The time complexity of bottom-up merge sort is also O(n log n) in the worst, average, and best cases. However, the space complexity is lower than in the recursive implementation because it does not require as much temporary storage for the merge step. Additionally, the bottom-up merge sort implementation has a better cache performance compared to the recursive implementation because it accesses the array elements in a contiguous manner, which can improve the speed of the algorithm on some systems.