Algorithm that combines insertion sort and merge sort. Wiki link
More...
#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <memory>
|
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...
|
|
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
◆ 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 |
41 for (i = start; i <
end; i++) {
44 while (j > start && temp < ptr[j - 1]) {
◆ main()
Main function.
- Returns
- 0 on exit
◆ 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 |
68 size_t firstIndex =
min;
69 size_t secondIndex = mid + 1;
71 auto ptr = array->
data();
75 for (
size_t index = min; index <=
max; index++) {
77 if (firstIndex <= mid &&
78 (secondIndex > max || ptr[firstIndex] <= ptr[secondIndex])) {
79 tempArray[index] = ptr[firstIndex];
82 tempArray[index] = ptr[secondIndex];
88 memcpy(ptr + min, tempArray.data() + min, (max - min) *
sizeof(T));
◆ 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 |
110 if ((max - min) <= threshold) {
114 size_t mid = (
max +
min) >> 1;
121 merge(array, min, max, mid);
◆ test()
Function to test code using random arrays.
- Returns
- none
133 constexpr
size_t size = 30;
136 for (
int i = 0; i < size; i++) {
146 for (
int i = 0; i < size; ++i) {