c++ example code to implement two way merge sort

2 way merge sort

The basic idea

Two-way merge sort is the merging of two ordered subtables into an ordered table. First, we have to have an algorithm for merging: two ordered tables are placed next to each other in the same array. arr[left] through ES9en-1 is the first ordered table, and arr[center] through right [right] is the second ordered table. Take one from each end for comparison, put the smaller one into an temp array, put the rest of the comparison directly into temp, and finally copy temp back to arr. This is zhi.
The so-called "sub", is to recursively merge and sort the first half of the data and the second half respectively.

Algorithm analysis

The time complexity of merging each round is O(n), which needs to be carried out in total ⌈ log2n & # 8969; Visit. The time complexity of the corresponding algorithm is O(nlog2n). The spatial complexity of merge sort is O(n). In addition, the merge algorithm in merge sort does not change the relative order of elements of the same keyword, so merge sort is stable.
The premise of 2-way merge sort is that the two sequences themselves are ordered.

void Merger(int *arr, int len, int width)
{
 int *temp =(int *)malloc(sizeof(int) * (len));
 // The two subscripts are initialized separately 
 int l1 = 0;
 int h1 = l1 + width - 1;
 int l2 = h1 + 1;
 int h2 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
 int temppos = 0;
 // Determines the value of the subscript 
 while (l1 < len && l2 < len)
 {
 while (l1 <= h1 && l2 <= h2)
 {
  if (arr[l1] < arr[l2])
  {
  temp[temppos++] = arr[l1++];
  }
  else
  {
  temp[temppos++] = arr[l2++];
  }
 }
 //l1 Have a rest 
 while (l1 <= h1)
 {
  temp[temppos++] = arr[l1++];
 }
 //l2 Have a rest 
 while (l2 <= h2)
 {
  temp[temppos++] = arr[l2++];
 }
 //l1 l2 Move back 
 l1 = h2 + 1;
 h1 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
 l2 = h1 + 1;
 h2 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
 }
 // Odd merges   The rest of the 1 A single block operation 
 while (l1 <len)
 {
 temp[temppos++] = arr[l1++];
 }
 // with temp cover arr
 for (int i = 0; i < len ; ++i)
 {
 arr[i] = temp[i];
 }
// free(temp);
}
void MergeSort(int *arr, int len)
{
 for (int i = 1; i < len; i *= 2)
 {
 Merger(arr, len, i);
 }
}
void show(int *arr, int len)
{
 for (int i = 0; i < len; ++i)
 {
 cout << arr[i] << " ";
 }
}
int main()
{
 int array[] = { 12, 51, 1, 36, 98, 21, 38, 47 };
 int len = sizeof(array) / sizeof(array[0]);
 MergeSort(array, len);
 show(array, len);
 system("pause");
 return 0;
}

PS:2 way merge sort algorithm

#include<iostream>
using namespace std;
class SortableList
{
public:
	SortableList(int mSize)
	{
		maxSize = mSize;
	  l= new int[maxSize];
		n = 0;
	}
	~SortableList()
	{
		delete[]l;
	}
	void Merge(int, int, int);
	void MergeSort(int,int);
	void Input();
	void Output();
	
   private:
		 int* l;
		 int maxSize;
		 int n;

};
void SortableList::Input()
{
	cout << " Please enter the number to sort: ";
	for (int i = 0; i <= maxSize - 1; i++)
		cin >> l[i];
}
void SortableList::Output()
{
	cout << " The sorted number is: ";
	for (int i = 0; i <= maxSize - 1; i++)
		cout << l[i]<<' ';
}
void SortableList::MergeSort(int left,int right)
{
	if (left < right)// If the sequence length is greater than 1 Is divided into 
	{
		int mid = (left + right) / 2;
		MergeSort(left, mid);// Sort the left sequence 
		MergeSort(mid + 1, right);// Sort the right sequence 
		Merge(left, mid, right);// merge 
	}
}
void SortableList::Merge(int left, int mid, int right)
{
	int* temp= new int[right - left + 1];
	int i = left, j = mid + 1, k = 0;
	while ((i <= mid) && (j <= right))// Determine if the sequence is empty 
		if (l[i] <= l[j])
			temp[k++] = l[i++];
		else temp[k++] = l[j++];
	while (i <= mid)
		temp[k++] = l[i++];// The right sequence is empty and the left sequence is written 
	while (j <= right)
		temp[k++] = l[j++];// Left sequence empty and right sequence written in turn 
	for (i = 0, k = left; k <= right;)
		l[k++] = temp[i++];// Temporary in array temp Put the sorted data into an array l
}
int main()
{
	int m;
	cout << " Please enter the number of Numbers to sort: ";
	cin >> m;
	SortableList a1(m);
	a1.Input();
	a1.MergeSort(0, m-1);
	a1.Output();
}