Introduction

Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into two halves, sorting each half, and then merging the sorted halves back together. This approach ensures that the array is sorted in O(n log n) time complexity.

Program Structure

The Merge Sort algorithm consists of two main functions:

• merge_sort(arr): This function recursively divides the array into halves until it can no longer be divided.
• merge(left, right): This function merges two sorted arrays into a single sorted array.

Python Code

def merge_sort(arr):
    """Sorts an array using the merge sort algorithm.

    Args:
        arr (list): The array to be sorted.

    Returns:
        list: A new sorted array.
    """
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

def merge(left, right):
    """Merges two sorted arrays into one sorted array.

    Args:
        left (list): The first sorted array.
        right (list): The second sorted array.

    Returns:
        list: A merged and sorted array.
    """
    sorted_array = []
    i = j = 0

    # Merge the two arrays
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    # Collect any remaining elements
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])

    return sorted_array

# Example usage
if __name__ == "__main__":
    array = [38, 27, 43, 3, 9, 82, 10]
    sorted_array = merge_sort(array)
    print("Sorted array:", sorted_array)

Explanation of the Code

The merge_sort function checks if the length of the array is less than or equal to one; if so, it returns the array as it is already sorted. It then finds the midpoint of the array, recursively sorts the left and right halves, and merges them using the merge function.

The merge function initializes two pointers, i and j, to track the current index of the left and right arrays, respectively. It compares the elements pointed to by these indices and appends the smaller element to the sorted_array. Once all elements from one of the arrays have been added, it appends any remaining elements from the other array.

Conclusion

Merge Sort is an efficient, stable sorting algorithm that works well for large datasets. Its O(n log n) time complexity makes it a preferred choice in many applications.