Merge Sort Using Python

Merge sort is a sorting algorithm that uses the divide-and-conquer approach to sort a list. It works by dividing the list into smaller sublists, sorting each sublist, and then merging the sorted sublists back together.

Here is an implementation of merge sort in Python:

def merge_sort(lst):
    # Base case: if the list has fewer than two elements, it is already sorted
    if len(lst) < 2:
        return lst
    
    # Split the list into two equal-sized sublists
    mid = len(lst) // 2
    left = lst[:mid]
    right = lst[mid:]
    
    # Recursively sort the sublists
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # Merge the sorted sublists and return the result
    return merge(left_sorted, right_sorted)

def merge(left, right):
    # Initialize the merged list and the indices for the left and right lists
    merged = []
    left_index = 0
    right_index = 0
    
    # Iterate through the left and right lists and add the smaller element to the merged list
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    
    # Add the remaining elements of the left or right list (if any) to the merged list
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    
    return merged

# Test the merge sort function
lst = [5, 4, 3, 2, 1]
print(merge_sort(lst))  # Output: [1, 2, 3, 4, 5]

Using Recursion

def merge_sort_recursive(lst):
    # Base case: if the list has fewer than two elements, it is already sorted
    if len(lst) < 2:
        return lst
    
    # Split the list into two equal-sized sublists
    mid = len(lst) // 2
    left = lst[:mid]
    right = lst[mid:]
    
    # Recursively sort the sublists
    left_sorted = merge_sort_recursive(left)
    right_sorted = merge_sort_recursive(right)
    
    # Merge the sorted sublists and return the result
    return merge(left_sorted, right_sorted)

def merge(left, right):
    # Initialize the merged list and the indices for the left and right lists
    merged = []
    left_index = 0
    right_index = 0
    
    # Iterate through the left and right lists and add the smaller element to the merged list
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    
    # Add the remaining elements of the left or right list (if any) to the merged list
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    
    return merged

# Test the merge sort function
lst = [5, 4, 3, 2, 1]
print(merge_sort_recursive(lst))  # Output: [1, 2, 3, 4, 5]

This implementation of merge sort works in the same way as the iterative version, but it uses recursion to sort the sublists instead of using a loop. The base case for the recursion is when the list has fewer than two elements, in which case the list is already sorted.

Merge sort has a time complexity of O(n log n) in the worst case, which makes it a faster alternative to bubble sort and selection sort for large lists. It is also a stable sort, which means that the order of elements with equal keys is preserved. However, it requires additional memory to store the sublists during the sorting process, so it may not be the best choice for sorting very large lists on a limited memory budget.