# Merge sort

#### Stable: Yes

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

## C++/C example

```
//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;

//creating random number generator
srand (time(NULL));

//get the size of array
int size = (sizeof(A)/sizeof(A));

//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;
}

```

## Summary

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.