There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply () below!

Agree with a comment or answer? Like () to up-vote the contribution!

When generating the middle index, how come we write middle_index = len(items) // 2 instead of middle_index = len(items) - 1 // 2 ? My concern here is that len(items) is not a valid index in items while len(items) - 1 is (it’s the last element in items). Thank you for your help.

You’re right that Len(items) isn’t a valid index, but that’s fine. The code never tries to access items[len(items)]. So we never run into the problem of accessing a non-existent index. Meanshile, “len(items)” gives us the number of items in the list, and so “len(items)//2” gives us exactly half the number of items (rounded down, if necessary). That works out neatly with the way that list-slicing works, and wherever possible, it gives us exactly half the list on the left, and half the list on the right.

In the worst case scenario, imagine a list of length 2:
. my_list = [“A”, “B”].

If we use “middle_index = (len(items)-1)//2” then middle index evaluates to 0.
(Try (2-1)//2 in python. You’ll see it evaluates to 0)

So you’d end up with:
. left_list = items[0:0] (Which is an empty list)
. right list = items[0:2] (Which is whole original list)

Done this way, you haven’t split the list at all, and the algorithm becomes an infinite loop that never terminates.

Recursion (repeatedly calling a function on itself, with a defined endpoint to prevent an infinite loop) effectively does the work of the for (or while) loop for us. Every recursive function can be written as an iterative function (i.e., one using while or for loops).

As a simpler example, look at the function generally used to introduce recursion: a function to generate the nth Fibonacci number (Beginning with the sequence 0, 1, every succeeding number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21 …)

# Here is the recursive version:
def fib_recur(n):
if n < 2:
return n
return fib_recur(n-1) + fib_recur(n-2)
print(fib_recur(8))
# 21
# ... and here is the iterative version:
def fib_iter(n):
if n < 2:
return n
fib_1 = 0
fib_2 = 1
for i in range(n -1):
fib = fib_1 + fib_2
fib_1 = fib_2
fib_2 = fib
return fib
print(fib_iter(8))
# 21

The point is that the recursive version, by repeatedly calling itself until certain conditions are met (in this case n < 2) accomplishes something that otherwise requires a for (or while) loop.

You can find both recursive and iterative versions of merge sort here.(Be sure to click the “Python” tabs.)

Why is the middle index len(items) // 2? I thought the index starts at 0. Let’s say that the length of items is 6. 6 //2 is 3. But that would be index 2:

The second step (“Create another variable called left_split . This should be a list of all elements in the input list starting at the first up to but not including the middle_index element.”) does not accept [0:middle_index] as correct, only [:middle_index]. Aren’t those the same thing?

We write middle_index = len(items) // 2 because say we have a list like my_list = [0,1,2,3,4]. The length of this list is 5 and therefore the middle index is 2 with the value ‘2’. Using integer division, it rounds down so 5 divided by 2 is 2.5 but by using integer division (//), this is rounded down to 2 which then correctly gives the middle index.

The course prerequisites should have included the Learn Recursion with Python course; this sorting algorithm uses recursion. I have done the Learn Recursion with Python.