Merge Sort Algorithm in Python.

MergeSort is a popular sorting algorithm known for its efficiency and stability. It operates by dividing the unsorted list into smaller sub-lists and then merging them back together to produce a sorted list. It is very similar to the Quick Sort Algorithm. In this article, we are going to understand the Merge Sort algorithm in detail with Python code implementation.

Merge Sort Algorithm Explanation.

The merge sort algorithm is based on the divide and conquer approach in which we continuously divide the given list into smaller units to create sorted sub-lists and then merge them back to create a final sorted list.  

 

Algorithm Steps:

• Start with an unsorted list/array.
• Divide the list into smaller sub-lists recursively until each sub-list contains only one element. This process is achieved recursively.
• Combine the smaller sorted sub-lists back together by comparing and merging adjacent pairs of sub-lists.
• Merge these pairs in a sorted manner to create larger sorted sub-lists. 

Python Program for Merge Sort Algorithm.

Below is the code implementation of Merge Sort Algorithm in Python:

# Python code implementation of Merge Sort
def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle of the list
        mid = len(arr) // 2 
 
        # Divide the list into two halves
        left_half = arr[:mid]  
        right_half = arr[mid:]

        # Recursive call to sort the left half
        merge_sort(left_half)  
        
        # Recursive call to sort the right half
        merge_sort(right_half)  

        # Merge the sorted halves
        i = j = k = 0  # Initialize indices for merging
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for remaining elements in left and right halves

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
arr = [64, 34, 25, 12, 20, 10, 90]
merge_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [10, 12, 20, 25, 34, 64, 90]

Time Complexity: Merge Sort demonstrates a time complexity of O(n log n) across all cases. This efficiency makes Marge Sort highly desirable for sorting larger datasets. 

Space Complexity: O(n). Merge Sort's space complexity primarily involves auxiliary space for temporary arrays during the merging phase.