Merge sort

Best Case: nlogn

Average Case: nlogn

Worst Case: nlogn

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

                

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.