9

Merge Sort Implementation In C++

 2 years ago
source link: https://www.journaldev.com/56329/merge-sort-in-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Merge Sort Implementation In C++

Filed Under: C++

In this article, we will learn about merge sort implementation in C++. Merge Sort is a popular Divide and Conquer algorithm that sorts a data structure very efficiently. This technique is widely used for sorting raw data and processing it. Let’s quickly have a look at some of the most popular sorting methods that are readily employed for data sorting.

Popular Sorting Methods

Note: The STL(Standard Template Library) uses a combination of Quick Sort and Hoare’s Partitioning method to sort the data.

What is Merge Sort in C++?

Merge sort is a well-known sorting algorithm that is known for being a time-efficient sorting method. This technique is a Divide and Conquer algorithm which means, it doesn’t sort the vector in one go, iterating over it again and again. Rather, it keeps on dividing the vector into smaller and smaller unsorted vectors, and recursively sort these smaller subproblems and merge them again into the final vector.

Let’s go through the algorithm step-by-step.

1. Merge_Sort() Function

Base Case: We start by checking the size of the vector. If the size is smaller than or equal to two, we have two base cases to deal with this situation.

  1. It can either be a single element vector i.e. start == end
  2. Or is should be a two element vector i.e. start + 1 == end.

Simply return from here, we will handle these cases in the merge() function

Not A Base Case: If the call didn’t hit the base case, then we proceed as follow

Step 1: Divide the vector into two smaller vectors.

int mid = (start + end)/2;
vector1 = start ->mid;
vector2 = mid + 1 -> end;

Note: We always divide the vector into two halves about its midpoint.

Step 2: Sort the smaller unsorted vectors

merge_sort(vector, start, mid);
merge_sort(vector, mid + 1, end);

This is a recursive approach to sort both the smaller unsorted vectors recursively. We use recursion to solve all the smaller subproblems.

Step 3: Merge these sorted vectors again to generate the final sorted vector.

merge(vector, start, end);

This marks the last step of our algorithm, and we return from the function call.

2. Merge() Function

The algorithm is currently incomplete because the merge function is not yet defined. Let’s learn the concept behind the merge function.

Step 1: Find the middle element

int mid = (start + end)/2;

Step 2: Create a temporary vector/array to store the newly generated sorted array.

int temp[100];

The size of the array is taken as 100 assuming that the total number of elements is always less than or equal to 100. However, we can also use a dynamic array for this purpose as follows.

int * temp = new int(1000);

Using this method gives an advantage of lesser memory consumption because later we can delete this locally generated variable if we want.

delete temp;

Step 3: Start filling the temporary array in a sorted manner.

int i = start;
int j = mid + 1;
int k = start;
// creating a dynamic temporary array
int *temp = new int(100);
// sorting logic
while(i <= mid && j <= end)
{
if (v[i] < v[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}

The following example demonstrates the implementation of the merge sort algorithm.

Merge Sort in C++ ExampleMerge Sort Example

Merge Sort Implementation In C++

Now let’s quickly dive into the code of the merge sort algorithm.

void merge(int *v, int start, int end)
{
// find the mid point
int mid = (start + end)/2;
// initialize the loop variables
int i = start;
int j = mid + 1;
int k = start;
// creating a dynamic temporary array
int *temp = new int(100);
while(i <= mid && j <= end)
{
if (v[i] < v[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
// copy all the elements back into the array
for(i = start; i < end; i++)
v[i] = temp[i];
}
void merge_sort(int *v, int start, int end)
{
// base case
if(start >= end)
return;
// follow 3 steps
// 1. divide
int mid = (start + end)/2;
// recursively sort the two arrays
merge_sort(v, start, mid);
merge_sort(v, mid + 1, end);
// merge the two smaller arrays
merge(v, start, end);
}
Merge Sort AlgorithmMerge Sort Algorithm

Time And Space Complexity Analysis

Let N denote the total number of elements to be sorted. Each vector is further divided into two halves until the base case is hit. And do a linear amount of work on both these smaller vectors(merge function takes O(N) time). The total number of smaller vectors generated from a vector of size N is log2N. Hence the total amount of time needed is Nlog2N units.

Time Complexity: O(Nlog2N)

Below is the recursion tree for the merge_sort() function

Merge Sort Recursion TreeMerge Sort Recursion Tree

We do not need any additional space for the merge_sort() function. However, we do need additional space for the merge() function. The space required for the merge() function is linear. Hence the total additional space required by the merge sort algorithm is N units.

Space Complexity: O(N)

Conclusion

In this article, we learned about the merge sort algorithm. We learned that this algorithm is one of the most time-optimal algorithms having a time complexity of O(Nlog2N). We further looked at its concept and implementation using C++. That’s it for today, stay healthy stay safe.

References

To learn more about the merge sort algorithm, you can visit the following websites.

https://en.wikipedia.org/wiki/Merge_sort


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK