merge sort Algorithm
Merge sort is a highly efficient, stable, and comparison-based sorting algorithm that employs the divide and conquer strategy. It works by recursively dividing the unsorted array or list into two equal halves, sorting each half individually, and then merging them back together into a single sorted array. This process of dividing, sorting, and merging continues until the entire array is sorted. The primary advantage of merge sort is its ability to handle large data sets with a time complexity of O(n log n), making it significantly faster than many other sorting algorithms, such as bubble sort and insertion sort.
The merge sort algorithm begins by dividing the input array into two halves. Each half is then sorted recursively using the same merge sort algorithm. Once both halves are sorted, they are combined or merged back together in a manner that maintains their sorted order. This merging process involves iterating through each element in the two halves and comparing them, selecting the smaller element and placing it in the sorted array. This comparison and selection process continues until all elements from both halves have been placed in the sorted array. The merge step is a crucial aspect of the merge sort algorithm, as it ensures that the combined array remains sorted. The process of dividing, sorting, and merging is repeated until the entire array is sorted, resulting in a highly efficient and reliable sorting algorithm that is particularly well-suited for handling large data sets.
//
// C++ implementation of merge sort
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/sorting
// https://github.com/allalgorithms/cpp
//
// Contributed by: Carlos Abraham Hernandez
// Github: @abranhe (abraham@abranhe.com)
//
#include <iostream>
// Merge the two half into a sorted data.
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int* L = new int[n1];
int* R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
delete[] L;
delete[] R;
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void merge_sort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
// A utility function to print an array of size n
void print_array(int arr[], int n)
{
for (size_t i = 0; i < n; i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
std::cout << "Unsorted array:" << std::endl;
print_array(arr, arr_size);
merge_sort(arr, 0, arr_size - 1);
std::cout << "Sorted array:" << std::endl;
print_array(arr, arr_size);
return 0;
}
