# 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.