Merge Sort, Quicksort and Divide-n-Conquer Algorithms in Python

Data Structures and Algorithms in Python is a beginner-friendly introduction to common data structures (linked lists, stacks, queues, graphs) and algorithms (search, sorting, recursion, dynamic programming) in Python, designed to help you prepare for coding interviews and assessments.

This tutorial is an executable Jupyter notebook. Click the Run on Colab button at the top of this page to execute the code.

Jupyter Notebooks: This notebook is made of cells. Each cell can contain code written in Python or explanations in plain English. You can execute code cells and view the results instantly within the notebook. Jupyter is a powerful platform for experimentation and analysis. Don't be afraid to mess around with the code & break things - you'll learn a lot by encountering and fixing errors. You can use the "Kernel > Restart & Clear Output" menu option to clear all outputs and start again from the top.

Problem

In this notebook, we'll focus on solving the following problem:

QUESTION 1: You're working on a new feature on Jovian called "Top Notebooks of the Week". Write a function to sort a list of notebooks in decreasing order of likes. Keep in mind that up to millions of notebooks can be created every week, so your function needs to be as efficient as possible.

The problem of sorting a list of objects comes up over and over in computer science and software development, and it's important to understand common approaches for sorting, and the trade-offs they offer. Before we solve the above problem, we'll solve a simplified version of the problem:

QUESTION 2: Write a program to sort a list of numbers.

"Sorting" usually refers to "sorting in ascending order", unless specified otherwise.

The Method

Here's a systematic strategy we'll apply for solving problems:

1. State the problem clearly. Identify the input & output formats.
2. Come up with some example inputs & outputs. Try to cover all edge cases.
3. Come up with a correct solution for the problem. State it in plain English.
4. Implement the solution and test it using example inputs. Fix bugs, if any.
5. Analyze the algorithm's complexity and identify inefficiencies, if any.
6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

1. State the problem clearly. Identify the input & output formats.

Problem

We need to write a function to sort a list of numbers in increasing order.

Input

1. nums: A list of numbers e.g. [4, 2, 6, 3, 4, 6, 2, 1]

Output

2. sorted_nums: The sorted version of nums e.g. [1, 2, 2, 3, 4, 4, 6, 6]

The signature of our function would be as follows:

2. Come up with some example inputs & outputs.

Here are some scenarios we may want to test out:

1. Some lists of numbers in random order.
2. A list that's already sorted.
3. A list that's sorted in descending order.
4. A list containing repeating elements.
5. An empty list.
6. A list containing just one element.
7. A list containing one element repeated many times.
8. A really long list.

Let's create some test cases for these scenarios. We'll represent each test case as a dictionary for easier automated testing.

To create the final test case (a really long list), we can start with a sorted list created using range and shuffle it to create the input.

3. Come up with a correct solution. State it in plain English.

It's easy to come up with a correct solution. Here's one:

1. Iterate over the list of numbers, starting from the left
2. Compare each number with the number that follows it
3. If the number is greater than the one that follows it, swap the two elements
4. Repeat steps 1 to 3 till the list is sorted.

We need to repeat steps 1 to 3 at most n-1 times to ensure that the array is sorted. Can you explain why? Hint: After one iteration, the largest number in the list is moved to the end of list.

This method is called bubble sort, as it causes smaller elements to bubble to the top and larger to sink to the bottom. Here's a visual representation of the process:

4. Implement the solution and test it using example inputs.

The implementation is straightforward. We'll create a copy of the list inside our function, to avoid changing it while sorting.

Notice how we're a tuple assignment to swap two elements in a single line of code.

Let's test it with an example.

We can evaluate all the cases together using the evaluate_test_cases helper function.

Great, looks like all our test cases passed! Although the last test case (a list of 10,000 numbers) took about 12 seconds to execute.

5. Analyze the algorithm's complexity and identify inefficiencies

The core operations in bubble sort are "compare" and "swap". To analyze the time complexity, we can simply count the total number of comparisons being made, since the total number of swaps will be less than or equal to the total number of comparisons (can you see why?).

for _ in range(len(nums) - 1):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            nums[i], nums[i+1] = nums[i+1], nums[i]

There are two loops, each of length n-1, where n is the number of elements in nums. So the total number of comparisons is $(n-1)*(n-1)$ i.e. $(n-1)^2$ i.e. $n^2 - 2n + 1$.

Expressing this in the Big O notation, we can conclude that the time complexity of bubble sort is $O(n^2)$ (also known as quadratic complexity).

Exercise: Verify that the bubble sort requires $O(1)$ additional space.

The space complexity of bubble sort is $O(n)$, even thought it requires only constant/zero additional space, because the space required to store the inputs is also considered while calculating space complexity.

As we saw from the last test, a list of 10,000 numbers takes about 12 seconds to be sorted using bubble sort. A list of ten times the size will 100 times longer i.e. about 20 minutes to be sorted, which is quite inefficient. A list of a million elements would take close to 2 days to be sorted.

The inefficiency in bubble sort comes from the fact that we're shifting elements by at most one position at a time.

Insertion Sort

Before we look at explore more efficient sorting techniques, here's another simple sorting technique called insertion sort, where we keep the initial portion of the array sorted and insert the remaining elements one by one at the right position.

Exercises:

1. Read the source code of the insertion_sort function and describe the algorithm in plain English. Reading source code is an essential skill for software development.
2. Determine the time and space complexity of insertion sort. Is it any better than bubble sort? Why or why not?

6. Apply the right technique to overcome the inefficiency. Repeat Steps 3 to 6.

To performing sorting more efficiently, we'll apply a strategy called Divide and Conquer, which has the following general steps:

1. Divide the inputs into two roughly equal parts.
2. Recursively solve the problem individually for each of the two parts.
3. Combine the results to solve the problem for the original inputs.
4. Include terminating conditions for small or indivisible inputs.

Here's a visual representation of the strategy:

Merge Sort

Following a visual representation of the divide and conquer applied for sorting numbers. This algorithm is known as merge sort:

7. Come up with a correct solution. State it in Plain English.

Here's a step-by-step description for merge sort:

1. If the input list is empty or contains just one element, it is already sorted. Return it.
2. If not, divide the list of numbers into two roughly equal parts.
3. Sort each part recursively using the merge sort algorithm. You'll get back two sorted lists.
4. Merge the two sorted lists to get a single sorted list

Can you guess how the "merge" operation step 4 works? Hint: Watch this animation: https://youtu.be/GW0USDwhBgo?t=28

QUESTION 3: Write a function to merge two sorted arrays.

Try to explain how the merge operation works in your own words below:

1. ???
2. ???
3. ???
4. ???

8. Implement the solution and test it using example inputs

Let's implement the merge sort algorithm assuming we already have a helper function called merge for merging two sorted arrays.

Two merge two sorted arrays, we can repeatedly compare the two least elements of each array, and copy over the smaller one into a new array.

Here's a visual representation of the merge operation:

Let's test the merge operation, before we test merge sort.

It seems to work as expected. We can now test the merge_sort function.

Let's test all the cases using the evaluate_test_cases function.

All the test cases have passed! Our function works as expected.

Notice the last test case, the merge sort function took just 50 milliseconds to sort 10,000 numbers, which took bubble sort about 12 seconds.

9. Analyze the algorithm's complexity and identify inefficiencies

Analyzing the complexity of recursive algorithms can be tricky. It helps to track and follow the chain of recursive calls. We'll add some print statements to our merge_sort and merge_functions to display the tree of recursive function calls.

We can now see that each merge_sort call itself invokes merge_sort twice (but with an array half the size), and also invokes the merge function once to merge the two resulting arrays. The two calls to merge_sort themselves make two recursive calls followed by an invocation of merge. The division continues till we reach an list of size 1 or 0. Thus, the merge sort algorithm ultimately boils down to a series of merge operations performed on arrays of varying sizes. Inside the merge function we perform comparisons and add numbers to a new array.

Exercise: Verify that time complexity of the merge operation is $O(n)$, where $n$ is the sum of the sizes of the two input lists. Hint: Count the number of comparisons.

To find the overall complexity of merge_sort, we simply need to count how many times the merge function was invoked and the size of the input list for each invocation. Here's how all the subproblems can be visualized:

Counting from the top and starting from 0, the $k^{th}$ level of the above tree involves $2^k$ invocations of merge with sublists of size roughly $n / 2^k$, where $n$ is the size of the original input list. Therefore the total number of comparisons at each level of the tree is $2^k * n/2^k = n$.

Thus, if the height of the tree is $h$, the total number of comparisons is $n*h$. Since there are $n$ sublists of size 1 at the lowest level, it follows that $2^{(h-1)} = n$ i.e. $h = \log n + 1$. Thus the time complexity of the merge sort algorithms is $O(n \log n)$.

As we already saw, it took just 50 ms to sort an array of 10,000 elements. Even an array of 1 million elements will take only a few seconds to be sorted.

Space Complexity

To find the space complexity of merge sort, it helps to recall that a new list with equal to the sum of the sizes of the two lists is created in each invocation of merge.

i, j, merged = 0, 0, []
while i < len(nums1) and j < len(nums2):
    if nums1[i] <= nums2[j]:
        merged.append(nums1[i])
        i += 1
    else:
        merged.append(nums2[j])
        j += 1

At first glance, it may seem that $O(n)$ space is required for each level of the tree, so the space complexity of merge sort is $O(n \log n)$.

However, since the original sublists can be discarded after the merge operation, the additional space can be freed or reused for future merge calls. Thus, merge sort requires $O(n)$ additional space i.e. the space complexity is $O(n)$.

There are several extensions and variations and extensions of merge sort:

• K-way merge sort: https://en.wikipedia.org/wiki/K-way_merge_algorithm
• Counting inversions in an array: https://www.geeksforgeeks.org/counting-inversions/
• Merge sort and insertion sort hybrids: https://en.wikipedia.org/wiki/Timsort

10. Apply the right technique to overcome the inefficiency. Repeat Steps 3 to 6.

The fact that merge sort requires allocating additional space as large as the input itself makes it somewhat slow in practice because memory allocation is far more expensive than comparisons or swapping.

Quicksort

To overcome the space inefficiencies of merge sort, we'll study another divide-and-conquer based sorting algorithm called quicksort, which works as follows:

1. If the list is empty or has just one element, return it. It's already sorted.
2. Pick a random element from the list. This element is called a pivot.
3. Reorder the list so that all elements with values less than or equal to the pivot come before the pivot, while all elements with values greater than the pivot come after it. This operation is called partitioning.
4. The pivot element divides the array into two parts which can be sorted independently by making a recursive call to quicksort.

The key observation here is that after the partition, the pivot element is at its right place in the sorted array, and the two parts of the array can be sorted independently in-place.

Here's an implementation of quicksort, assuming we already have a helper function called partitions which picks a pivot, partitions the array in-place, and returns the position of the pivot element.

Here's how the partition operation works(source):

Here's an implementation of partition, which uses the last element of the list as a pivot:

Let's see the partition function in action:

As expected the list was partitioned using 3 as the pivot element, which finally ends up at the index 2 within the partitioned list.

Exercise: Add print statements inside the partition function to display the list, the left pointer and the right pointer at the beginning and end of every loop, to study how the partitioning works.

We can now see quicksort in action:

Let's test all the cases using the evaluate_test_cases function.

All the test cases have passed successfully! You will also notice that is also marginally faster than merge sort for larger lists.

Time Complexity of Quicksort

If we assume that

Best case partitioning:

If we partition the list into two nearly equal parts, then the complexity analysis is similar to that of merge sort and quicksort has the complexity $O(n \log n)$. This is called the average-case complexity.

Worst case partitioning:

In this case, the partition is called n times with lists of sizes n, n-1... so that total comparisions are $n + (n-1) + (n-2) + ... + 2 + 1 = n * (n-1) / 2$. So the worst-case complexity of quicksort is $O(n^2)$.

Exercise: Verify that quicksort requires $O(1)$ additional space.

Despite the quadratic worst case time complexity Quicksort is preferred in many situations because its running time is closer to $O(n \log n)$ in practice, especially with a good strategy for picking a pivot. Some these are:

• Picking a random pivot
• Picking median of medians

Here are some other problems you can solve using the partitioning strategy of Quicksort: https://www.techiedelight.com/problems-solved-using-partitioning-logic-quicksort/

Custom Comparison Functions

Let's return to our original problem statement now.

QUESTION 1: You're working on a new feature on Jovian called "Top Notebooks of the Week". Write a function to sort a list of notebooks in decreasing order of likes. Keep in mind that up to millions of notebooks can be created every week, so your function needs to be as efficient as possible.

First, we need to sort objects, not just numbers. Also, we want to sort them in the descending order of likes. To achieve this, all we need is a custom comparison function to compare two notebooks.

Let's create a class that captures basic information about notebooks.

Let's create some sample notebooks

Next, we'll define a custom comparison function for comparing two notebooks. It will return the strings 'lesser', 'equal' or 'greater' to establish order between the two objects.

Note that we say nb1 is lesser than nb2 if it has higher likes, because we want to sort the notebooks in decreasing order of likes.

Here's an implementation of merge sort which accepts a custom comparison function.

As you can see, the notebooks are now sorted by likes. Since we have written a generic merge_sort function that works with any compare function, we can also use it to sort the notebooks by title.

Exercise: Implement and test generic versions of bubble sort, insertion sort and quicksort using the empty cells below.

Summary and Exercises

We've covered the following sorting algorithms in this tutorial:

1. Bubble sort
2. Insertion sort
3. Merge sort
4. Quick sort

There are several other sorting algorithms, and most languages provide library functions for sorting that use a hybrid approach depending on the size and type of element in the list/array.

Try out some problems on sorting and divide-n-conquer here:

• https://leetcode.com/tag/sort/
• https://www.techiedelight.com/sorting-interview-questions/
• HackerRank
• https://leetcode.com/tag/divide-and-conquer/
• https://www.geeksforgeeks.org/divide-and-conquer/

Use this problem solving template: https://github.com/JovianHQ/notebooks/blob/main/data-structures-and-algorithms-in-python/python-problem-solving-template.ipynb