The Self-Taught Computer Scientist

Figure 4.1: The first part of a merge sort

---

Introduction to Algorithms
46
Lists containing one item are sorted by definition. Once you have sorted lists containing one item 
each, you merge your sublists two at a time by comparing the first item in each list. Merging your lists 
means combining them in sorted order.
First, you merge [6] and [3], then you merge [9] and [2]. In this case, each list contains only one 
number, so you compare the two numbers and put the smallest number at the beginning of your new, 
merged list and the larger number at the end. Now, you have two sorted lists:
[3, 6], [2, 9]
Then, you merge these two lists:
# unmerged
[3, 6], [2, 9]
#merged
[]
First, you compare 3 and 2. Since 2 is smaller, it goes into your merged list:
# unmerged
[3, 6], [9]
#merged
[2]
Now you compare 3 and 9. Since 3 is smaller, it goes into your merged list:
# unmerged
[6], [9]
#merged
[2, 3]
Finally, you compare 6 and 9. Since 6 is smaller, it goes into your merged list. Then, you put the 
9 into the merged list:
# unmerged
[], []
#merged
[2, 3, 6, 9]
Now that you’ve finished all your merges, you have a single, sorted list.
Here is how to implement a merge sort in Python:
def merge_sort(a_list):
if len(a_list) > 1:

---

Chapter 4 Sorting Algorithms
47
mid = len(a_list) // 2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
left_ind = 0
right_ind = 0
alist_ind = 0
while left_ind < len(left_half) and right_ind < len(right_half):
if left_half[left_ind] <= right_half[right_ind]:
a_list[alist_ind] = left_half[left_ind]
left_ind += 1
else:
a_list[alist_ind] = right_half[right_ind]
right_ind += 1
alist_ind += 1
while left_ind < len(left_half):
a_list[alist_ind]=left_half[left_ind]
left_ind += 1
alist_ind += 1
while right_ind < len(right_half):
a_list[alist_ind]= right_half[right_ind]
right_ind += 1
alist_ind += 1
This part of your algorithm is responsible for breaking your lists into sublists:
if len(a_list) > 1:
mid = len(a_list) // 2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
left_ind = 0
right_ind = 0
alist_ind = 0
This part is responsible for merging two lists:
left_ind = 0
right_ind = 0
alist_ind = 0
while left_ind < len(left_half) and right_ind < len(right_half):
if left_half[left_ind] <= right_half[right_ind]:
a_list[alist_ind] = left_half[left_ind]

---