A Simplified Explanation of Merge Sort

Karuna Sehgal
Jan 25, 2018 · 3 min read

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written blog posts about Binary Search, Linear Search, Interpolation Search, Sorting Algorithms, Selection Sort, and Insertion Sort.

This blog post I will focus on Merge Sort. I will explain what Merge Sort is, how Merge Sort is associated with Algorithms, try to break down Merge Sort step by step and provide an example.

What is Merge Sort and how is it associated with Algorithms?

Merge Sort is a sorting algorithm, which is commonly used in computer science. Merge Sort is a divide and conquer algorithm. It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. So Merge Sort first divides the array into equal halves and then combines them in a sorted manner.

Merge Sort Algorithms: Steps on how it works:

  1. If it is only one element in the list it is already sorted, return.
  2. Divide the list recursively into two halves until it can no more be divided.
  3. Merge the smaller lists into new list in sorted order.

Below is an image of an array, which needs to be sorted. We will use Merge Sort Algorithm, to sort this array:

And here is another image and a YouTube video which provides an example of Merge Sort:

Merge Sort: An example

Here is an example of writing the Merge Sort Algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameter: an array. The function returns the sorted array.

Important Characteristics of Merge Sort:

  • Merge Sort is useful for sorting linked lists.
  • Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other.
  • Overall time complexity of Merge sort is O(nLogn). It is more efficient as it is in worst case also the runtime is O(nlogn)
  • The space complexity of Merge sort is O(n). This means that this algorithm takes a lot of space and may slower down operations for the last data sets.

Overall Merge Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over other sorting algorithms like quick sort.

Karuna Sehgal

Woman on a mission — to live the best life possible!!

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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