Merge Sort

Merge Sort

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the array into smaller subarrays, sorting them individually, and then merging them back together to obtain the final sorted array.

Here's a step-by-step explanation of the Merge Sort algorithm:


The merging process involves comparing the elements from the two halves and placing them in the correct order in a temporary array. Once all the elements have been merged, the temporary array is copied back to the original array.

The algorithm continues this process, dividing the array into smaller halves until each subarray contains only one element (which is already considered sorted). Then, it starts merging the sorted subarrays back together, gradually building the final sorted array.

Merge Sort has a time complexity of O(n log n), where n is the number of elements in the array. It is efficient for large datasets and guarantees a stable sorting (preserves the relative order of elements with equal values).

Merge Sort Code in Python

Here's an implementation of the Merge Sort algorithm in Python:

def merge_sort(arr):

    if len(arr) <= 1:

        return arr

    # Divide the array into two halves

    mid = len(arr) // 2

    left_half = arr[:mid]

    right_half = arr[mid:]

    # Recursively sort the two halves

    left_half = merge_sort(left_half)

    right_half = merge_sort(right_half)

    # Merge the sorted halves

    sorted_arr = merge(left_half, right_half)

    return sorted_arr


def merge(left, right):

    merged = []

    left_index = 0

    right_index = 0

    # Compare elements from the two halves and merge them

    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 any remaining elements from the left half

    while left_index < len(left):

        merged.append(left[left_index])

        left_index += 1

    # Add any remaining elements from the right half

    while right_index < len(right):

        merged.append(right[right_index])

        right_index += 1

    return merged

# Example usage:

array = [5, 2, 8, 1, 9, 3]

sorted_array = merge_sort(array)

print("Sorted array:", sorted_array)