Merge Sort in C++

What is Merge Sort in C++?

Merge sort is one the sorting technique that is used to sort the data in a logical order. It uses divide and conquer approach for sorting the data. Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list. In this article, we will read more about merge sort in C++.

merging
Time Complexity Θ(n Log n)
Best Case Ω(n Log n)
Worst Case O(n Log n)
Space Complexity O(n)

Merge Sort in C++

  • A file of any size can be sorted using merge sort.
  • Elements in the merge sort are divided into two sub list again and again until each sub-list contain only one element.
  • After this, the elements are merged to make a sorted list.
  • It requires more space and is less efficient
Merge Sort in C++

Execution of Merge sort in C++

Merge sort is executed in three steps:-

1.) Divide Step:

First of all the array will be divide in to  N sub list, until each sub list contains only one element.

2.) Conquer Step:

Take two sub list and place them in logical order.

3.) Combine Step:

Combine the elements back by merging the two sorted sub list into a sorted sequence.

Merge Sort in Cpp

Program for merge sort in C++

We will look at two different methods, both have the same time complexity with the difference that –

  • Method 1 – Uses two temp subarrays
  • Method 2 – Uses 1 temp subarray

The combined size of two temp subarrays in method 1 is the same as the whole array in method 2. So the space complexity remains the same.

Performance

Strengths

  • With a good time complexity of O(n log n), merge sort is great !!!
  • Good to learn Divide and conquer algorithm later used in Dynamic Programming concepts

Weakness

  • Poor space complexity of O(n)
  • Lots of overhead in copying data between arrays and making new arrays
Merge sort in C++ meme
Quiz time

Fun Fact

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).

2 comments on “Merge Sort in C++”