Learn practical skills, build real-world projects, and advance your career

Merge Sort, Quicksort and Divide-and-Conquer Algorithms

Helper Notebook: Link

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.

For question 2:

Stating the probelem clearly

We need to sort the list of numbers in ascending order.

Input and Output

Input: Input will be a list of numbers
Output: Output will be sorted list of numbers

Example inputs (Test Cases)

  1. A list numbers with more than two elements
  2. An empty list
  3. A list with single element
  4. A list with repeating numbers
  5. A list with one element repeated many times
  6. A list with decreasing elements
  7. A sorted list
  8. A really long list