Understanding the Merge Sort Algorithm

Introduction to Merge Sort

This tutorial will guide you through implementing the merge sort algorithm to sort an array of integers.

Step 1: Define the Problem and the Approach

We are given an array of integers and we need to sort it in ascending order. We will use the merge sort algorithm to solve this problem.

Step 2: Split the Array into Two Halves

We will split the array into two halves, each of which will be sorted recursively.

if len(array) <= 1:
    return array
mid = len(array) // 2
left_half = array[:mid]
right_half = array[mid:]

Step 3: Recursively Sort the Two Halves

We will recursively sort the two halves.

left_half = merge_sort(left_half)
right_half = merge_sort(right_half)

Step 4: Merge the Two Sorted Halves

We will merge the two sorted halves into a single sorted array.

return merge(left_half, right_half)

Step 5: Define the Merge Function

We will define a helper function to merge two sorted arrays into a single sorted array.

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0
    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
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged

Example Use Case

Here's an example use case:

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_half = array[:mid]
    right_half = array[mid:]
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    return merge(left_half, right_half)
def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0
    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
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged
array = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(array))  # Output: [11, 12, 22, 25, 34, 64, 90]