Implementation of MergeSort

MergeSort is a divide-and-conquer algorithm that works by recursively dividing the input array into two halves, sorting each half separately, and then merging the sorted halves to produce the final sorted array.

Here is a step-by-step implementation of MergeSort in Python:

{{code}}

In this implementation, the merge_sort() function takes an array arr as input and recursively sorts the elements using the MergeSort algorithm. The base case is when the length of the array is less than or equal to 1, in which case the array is already sorted.

The algorithm computes the middle index mid of the array and divides the array into two halves, left and right. It then recursively applies the MergeSort algorithm to the left and right halves.

The merge() function merges the sorted left and right halves to produce the final sorted array. It compares the elements from left and right and appends the smaller element to the result array. The pointer i is used to iterate through the elements of left, and the pointer j is used to iterate through the elements of right.

Finally, the function returns the sorted result array.

Let's see the implementation in action with an example. Consider the following unsorted array:

1arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]

xxxxxxxxxx

print(result)

# Implementation of MergeSort

​

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

    while i < len(left):

        result.append(left[i])

        i += 1

    while j < len(right):

        result.append(right[j])

        j += 1