Python: Merge Sort on Lists

1. Introduction

In this blog post, we will learn how to write a Python program to implement merge sort on a list.

Merge Sort is a classic divide-and-conquer sorting algorithm. It works by dividing the unsorted list into n sub-lists, each containing one element (which is considered sorted). Then, it repeatedly merges these sub-lists to produce new sorted sub-lists until there is only one sub-list left. This final sub-list is the sorted list.

2. Program Overview

In this program, we will:

1. Define a function to merge two halves of a list.

2. Define the main mergeSort function that divides the list and sorts each half.

3. Test the merge sort implementation on a sample list.

3. Code Program

def mergeSort(arr):
    # Base case: If the array has one or zero elements, it's already sorted.
    if len(arr) <= 1:
        return arr

    # Split the list in half
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Recursively sort both halves
    left_half = mergeSort(left_half)
    right_half = mergeSort(right_half)

    # Merge the sorted halves
    merged = []
    i = j = 0

    # Merge while there are elements in either left or right
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            merged.append(left_half[i])
            i += 1
        else:
            merged.append(right_half[j])
            j += 1

    # Add the remaining elements if any
    while i < len(left_half):
        merged.append(left_half[i])
        i += 1
    while j < len(right_half):
        merged.append(right_half[j])
        j += 1

    return merged

# Test the function
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = mergeSort(arr)
print("Original Array:", arr)
print("Sorted Array:", sorted_arr)

Output:

Original Array: [38, 27, 43, 3, 9, 82, 10]
Sorted Array: [3, 9, 10, 27, 38, 43, 82]

4. Step By Step Explanation

1. The list is recursively divided in half until we get sub-lists with only one element.

2. We then merge these sub-lists (which are sorted) to produce larger, fully sorted sub-lists.

3. This process is repeated until we merge all sub-lists into one single sorted list.