basecs
Published in

basecs

Making Sense of Merge Sort [Part 1]

Making sense of merge sort

Divide and conquer algorithms

Merge sort: a definition

The basic idea behind merge sort is this: it tends to be a lot easier to sort two smaller, sorted lists rather than sorting a single large, unsorted one.

Merge sort theory: how does it even?

Hang on for a second — we’re programmers! Intrinsically we know that, at the end of the day, there really is no magic at play here. There’s something else going on under the hood, and it’s probably an abstraction of something else.

  1. Divide and break up the problem into the smallest possible “subproblem”, of the exact same type.
  2. Conquer and tackle the smallest subproblems first. Once you’ve figured out a solution that works, use that exact same technique to solve the larger subproblems — in other words, solve the subproblems recursively.
  3. Combine the answers and build up the smaller subproblems until you finally end up applying the same solution to the larger, more complicated problem that you started off with!
The rules of divide and conquer algorithms

Spotting recursion in the (algorithm) wild

Merge sort: in practice
Step 1: Dividing
Step 2: Conquering!
How does merge sort work with recursion?

This is exactly what makes recursion so powerful: once we’ve figured out how to solve the problem of merging two lists together, it doesn’t matter if the list has one element, or a hundred — we can reuse the same logic in both scenarios.

Merge sort in action: step 1 — dividing
Merge sort in action: step 2 — merging

Recursion at work

How recursion works inside of an implementation of a mergeSort function
  1. a merge function, which actually combines two lists together and sorts them in the correct order
  2. and a mergeSort function, which will continue to split the input array again and again, recursively, and will also call merge again and again, recursively.
Recursive vs iterative solutions

Resources

  1. Binary Search & Merge Sort, Department of Computer Science, Carnegie Mellon University
  2. Mergesort, Ian Foster
  3. Merge Sort, Harvard CS50
  4. Merge sort algorithm, mycodeschool
  5. External Sorting, GeeksForGeeks

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store