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. More...
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. More...
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. More...
static void	test ()
	Function to test code using random arrays. More...
int	main ()
	Main function. More...

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