FAQ: Merge Sort: Python - Partitions

This community-built FAQ covers the “Partitions” exercise from the lesson “Merge Sort: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Sorting Algorithms

FAQs on the exercise Partitions

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 (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 (reply) below!

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

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

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.

1 Like

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.

2 Likes

How does the functioning keep on dividing the list?
We only spilt it once and returned the lst if the elements less than 2

It splits recursively, so each sub-list is split until len == 1. Step through this visualizer to see what’s going on.

Correct, but why aren’t we using loop for this?

@byteninja86485, have you studied recursion yet?

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:

0, 1, 2, 3, 4 ,5

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?

Why is this red flagged?

def merge_sort(items):
    length = len(items)

    if length <= 1:
        return items

    middle_index = length // 2

Did you define middle_index to be the length of items divided by 2 using integer division ( // )?

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.