Merge Sort in Python

  

Merge Sort

Merge Sort is an efficient, stable, and comparison-based sorting algorithm. It follows the divide-and-conquer paradigm by recursively dividing the unsorted list into two halves, sorting each half, and then merging the sorted halves to produce the final sorted list.

What is Merge Sort?

Merge Sort is a sorting algorithm that works by dividing the input array into two halves, recursively sorting each half, and then merging the sorted halves to produce the final sorted array.

Example:

• Unsorted List: [38, 27, 43, 3, 9, 82, 10]

• Sorted List: [3, 9, 10, 27, 38, 43, 82]

Solution:

Now let’s see how to implement Merge Sort in Python.

 # Function to merge two subarrays

def merge(arr, left, mid, right):

    n1 = mid - left + 1

    n2 = right - mid

    leftArr = arr[left:mid + 1]

    rightArr = arr[mid + 1:right + 1]

    i = j = 0

    k = left

    # Merge the temporary arrays

    while i < len(leftArr) and j < len(rightArr):

        if leftArr[i] <= rightArr[j]:

            arr[k] = leftArr[i]

            i += 1

        else:

            arr[k] = rightArr[j]

            j += 1

        k += 1

    # Copy remaining elements of leftArr[], if any

    while i < len(leftArr):

        arr[k] = leftArr[i]

        i += 1

        k += 1

    # Copy remaining elements of rightArr[], if any

    while j < len(rightArr):

        arr[k] = rightArr[j]

        j += 1

        k += 1

# Function to implement Merge Sort

def merge_sort(arr, left, right):

    if left < right:

        mid = (left + right) // 2

        # Recursively sort first and second halves

        merge_sort(arr, left, mid)

        merge_sort(arr, mid + 1, right)

        # Merge the sorted halves

        merge(arr, left, mid, right)

# Example usage

arr = [38, 27, 43, 3, 9, 82, 10]

print("Unsorted array:", arr)

merge_sort(arr, 0, len(arr) - 1)

print("Sorted array:", arr)

Explanation of Code:

Each code version defines a mergeSort function to sort an array using the Merge Sort algorithm.

• Divide: Recursively split the array into two halves until each subarray contains a single element.

• Conquer: Merge the sorted halves to produce

1. Merge Function: This function merges two subarrays of arr. It creates temporary arrays to hold the values of the left and right subarrays, then merges these arrays back into the original array.

2. Merge Sort Function: This function recursively divides the array into two halves, sorts each half, and merges them. The base case for the recursion is when the array has one or zero elements.

3. Main Function: This is the entry point of the program where the array is initialized and the mergeSort function is called.

Sample Input & Output:

Input:

• Unsorted array: [38, 27, 43, 3, 9, 82, 10]

Output:

• Sorted array: [3, 9, 10, 27, 38, 43, 82]

Conclusion:

        Merge Sort is an efficient sorting algorithm suitable for large datasets. It guarantees a time complexity of O(n log n) in all cases, making it a reliable choice for sorting operations.

**  Please do subscribe my blog for future updates and share with your friends, if you find this informative **