Implementation of Bottom Up Merge Sort

I've learned that Merge Sort is a sorting algorithm which follows the principle of Divide and Conquer and it have average time complexity as n(log n).

Here I've divided the array of size n in sub array (initializing with length 2) and conquered it by sorting the sub arrays. Then we proceed the range with multiple of 2 until it's less than length of the array (i.e. 2,4,8,....i where i<length of array).

When it exceeds length of array then function returns the sorted array.

I have used two functions to implement Merge Sort:

Merge Sort (To Produce Sub Array)

If length of array is less than range return array.
Recursion and increasing the range exponentially.

Insertion Sort (To Sort Sub Array)

Sort the element within the range using Insertion Sort. I've chosen insertion sort because it's more efficient than bubble sort and selection sort.

The program works fine and I would like to know whether I've understand the concept of merge sort and implemented it correctly?

//C++ Code
#include<iostream>

// Print
void print(int *arr, int length);

// To Sort the sub array
void insertion_sort(int *arr, int low, int high)
{
    for(int i = high; (i-1)>=low; i--)
    {
        if (arr[i] < arr [i-1])
        {
            int temp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = temp;
        }
    }
}

int *merge_sort(int* arr, int length, int index = 2)
{
    if (length <= index) // Terminating Condition
    {
        return arr;
    }

    // The range is defined by index.

        /*
            If array has 8 elements:  ********
            It will sort array until it's range within the length of array.
            1st call  2*1 elements max: ** ** ** ** // 2 set as default argument
            2nd call  2*2 elements max: **** ****
            3rd call  2*3 elements max: ********
            Returns Array
        */

    // The range is defined by index.

    for(int i=0; (i+index)<length; i+=index)
    {
        // Divide and Sort
        insertion_sort(arr, i, i+index);
    }

    // The range will increase in multiple of 2 (i.e. 2,4,8,....i where i<length of array)
    return merge_sort(arr, length, index*2);
}

int main()
{
    int length;    
    std::cout<<"Length of Array: ";
    std::cin>>length;

    int arr[length];

    for(int i=0; i<length; i++)
    {
        std::cout<<"Enter element "<<i+1<<" : ";
        std::cin>>arr[i];
    }

    int *result = merge_sort(arr, length);
    
    print(result, length);
    
    return 0;
}

void print(int *arr, int length)
{
    std::cout<<"Sorted Array: ";

    for(int i=0; i<length; i++)
    {
        std::cout<<arr[i]<<" ";
    }

    std::cout<<"\n";
}

Solution

A pure bottom up merge sort divides an array of n elements into n runs of size 1, then each pass merges even and odd runs. Link to wiki example:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

As suggested in the Wiki example comments, the direction of merge can be changed with each pass. To end up with sorted data in the original array, calculate the number of passes needed, and if the number of passes is odd, compare and swap (if needed) pairs of elements in place to create runs of size 2, then do the merge sort passes.

For a hybrid insertion + merge sort, do the same calculation for the number of passes, and if the number of passes is odd, set initial run size to 32 elements, otherwise, set initial run size to 64 elements. Do a single pass using insertion sort to sort the initial runs, then switch to merge sort.

Simple example code to get pass count (for 32 bit build, assumes n <= 2^31):

size_t GetPassCount(size_t n)               // return # passes
{
    size_t i = 0;
    for(size_t s = 1; s < n; s <<= 1)
        i += 1;
    return(i);
}