Merge sort is an efficient algorithm which is a divide and conquer algorithm. It is mostly stable makin it an ideal algorithm in many scenarios.

- Divides the array into n subarrays
- Merges the subarrays to create sorted subarays until all is left is the one subarray which is the sorted array

there are various ways to implement merge sort algorithms which all work the same but the structure is different, Here we have provided a C++ example of the merge sort algortihm

//Merges the two split arrays void merge(int *A, int low, int high, int mid) { int i, j, k, temp[high-low+1]; i = low; k = 0; j = mid + 1; //Loop to meger the arrays into a temporary array while (i <= mid && j <= high) { if (A[i] < A[j]) { temp[k] = A[i]; k++; i++; } else { temp[k] = A[j]; k++; j++; } } //Remaining values are inserted into i to midpoint then inserted into the temporary array while (i <= mid) { temp[k] = A[i]; k++; i++; } //Remaining values are inserted into j to midpoint then inserted into the temporary array while (j <= high) { temp[k] = A[j]; k++; j++; } for (i = low; i <= high; i++) { A[i] = temp[i-low]; } } //Function splits the array into two parts, high and low void sort(int *A, int low, int high) { int mid; if (low < high) { //array is split mid=(low+high) / 2; sort(A, low, mid); sort(A, mid+1, high); //once split it is sent to be sorted merge(A, low, high, mid); } } int main() { int random; //create an empty array with 100 elements int A[100]; //creating random number generator srand (time(NULL)); //get the size of array int size = (sizeof(A)/sizeof(A[0])); //loops through and inserts into array with a random int between 1-1000 for (int i = 0; i < size; i++) { random = rand() % 1000 + 1; A[i] = random; } //begin sorting sort(A, 0, size-1); //print through sorted array for (int i = 0; i < size; i++) { std::cout << A[i] << std::endl; } return 0; }

Very fast and reliable algorithm and is always nlogn in any scenario it's memory however is n meaning it can use up a fair bit of memory for very large data sets.