merge_insertion_sort.cpp File Reference

Algorithm that combines insertion sort and merge sort. Wiki link More...

#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <memory>

Include dependency graph for merge_insertion_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors
namespace	merge_insertion
	Combined Intersion-Merge sorting algorithm.

Functions
template<typename T , size_t N>
static void	sorting::merge_insertion::InsertionSort (std::array< T, N > *A, size_t start, size_t end)
	Insertion merge algorithm.
template<typename T , size_t N>
static void	sorting::merge_insertion::merge (std::array< T, N > *array, size_t min, size_t max, size_t mid)
	Perform merge of data in a window.
template<typename T , size_t N>
void	sorting::merge_insertion::mergeSort (std::array< T, N > *array, size_t min, size_t max, size_t threshold)
	Final combined algorithm. Algorithm utilizes sorting::merge_insertion::InsertionSort if window length is less than threshold, else performs merge sort recursively using sorting::merge_insertion::mergeSort.
static void	test ()
	Function to test code using random arrays.
int	main ()
	Main function.

Detailed Description

Algorithm that combines insertion sort and merge sort. Wiki link

Author

@sinkyoungdeok

Krishna Vedala

See also

Individual algorithms: insertion_sort.cpp and merge_sort.cpp

Function Documentation

InsertionSort()

template<typename T , size_t N>

static void sorting::merge_insertion::InsertionSort ( std::array< T, N > * A, size_t start, size_t end )

static

Insertion merge algorithm.

See also

insertion_sort.cpp

Template Parameters

T	array data type
N	length of array

Parameters

A	pointer to array to sort
start	start index of sorting window
end	end index of sorting window

                                                                       {
    size_t i = 0, j = 0;
    T *ptr = A->data();
 
    for (i = start; i < end; i++) {
        T temp = ptr[i];
        j = i;
        while (j > start && temp < ptr[j - 1]) {
            ptr[j] = ptr[j - 1];
            j--;
        }
        //   for (j = i; j > start && temp < ptr[j - 1]; --j) {
        //       ptr[j] = ptr[j - 1];
        //   }
 
        ptr[j] = temp;
    }
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    std::srand(std::time(nullptr));
    test();
    return 0;
}

Here is the call graph for this function:

merge()

template<typename T , size_t N>

static void sorting::merge_insertion::merge ( std::array< T, N > * array, size_t min, size_t max, size_t mid )

static

Perform merge of data in a window.

Template Parameters

T	array data type
N	length of array

Parameters

A	pointer to array to sort
min	start index of window
max	end index of window
mid	mid-point of window

                                                                             {
    size_t firstIndex = min;
    size_t secondIndex = mid + 1;
 
    auto ptr = array->data();
    std::array<T, N + 1> tempArray{0};
 
    // While there are elements in the left or right runs
    for (size_t index = min; index <= max; index++) {
        // If left run head exists and is <= existing right run head.
        if (firstIndex <= mid &&
            (secondIndex > max || ptr[firstIndex] <= ptr[secondIndex])) {
            tempArray[index] = ptr[firstIndex];
            firstIndex++;
        } else {
            tempArray[index] = ptr[secondIndex];
            secondIndex++;
        }
    }
 
    // transfer to the initial array
    memcpy(ptr + min, tempArray.data() + min, (max - min) * sizeof(T));
    //  for (int index = min; index <= max; index++) ptr[index] =
    //  tempArray[index];
}

Here is the call graph for this function:

mergeSort()

template<typename T , size_t N>

void sorting::merge_insertion::mergeSort	(	std::array< T, N > *	array,
		size_t	min,
		size_t	max,
		size_t	threshold )

Final combined algorithm. Algorithm utilizes sorting::merge_insertion::InsertionSort if window length is less than threshold, else performs merge sort recursively using sorting::merge_insertion::mergeSort.

Template Parameters

T	array data type
N	length of array

Parameters

A	pointer to array to sort
min	start index of sort window
max	end index of sort window
threshold	window length threshold

                                 {
    // prerequisite
    if ((max - min) <= threshold) {
        InsertionSort(array, min, max);
    } else {
        // get the middle point
        size_t mid = (max + min) >> 1;
 
        // apply merge sort to both parts of this
        mergeSort(array, min, mid, threshold);
        mergeSort(array, mid, max, threshold);
 
        // and finally merge all that sorted stuff
        merge(array, min, max, mid);
    }
}

Here is the call graph for this function:

test()

static void test ( )

static

Function to test code using random arrays.

Returns

none

                   {
    constexpr size_t size = 30;
    std::array<int, size> array{0};
    // input
    for (int i = 0; i < size; i++) {
        array[i] = std::rand() % 100 - 50;
        std::cout << array[i] << " ";
    }
    std::cout << std::endl;
 
    sorting::merge_insertion::InsertionSort(&array, 0, size);
    //  sorting::merge_insertion::mergeSort(&array, 0, size, 10);
 
    // output
    for (int i = 0; i < size; ++i) {
        std::cout << array[i] << " ";
    }
    std::cout << std::endl;
 
    assert(std::is_sorted(std::begin(array), std::end(array)));
    std::cout << "Test passed\n";
}

Here is the call graph for this function: