Algorithm that combines insertion sort and merge sort. Wiki link
More...
#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <memory>
|
namespace | sorting |
| for working with vectors
|
|
namespace | merge_insertion |
| Combined Intersion-Merge sorting algorithm.
|
|
|
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.
|
|
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 |
37 {
38 size_t i = 0, j = 0;
40
41 for (i = start; i <
end; i++) {
42 T temp = ptr[i];
43 j = i;
44 while (j > start && temp < ptr[j - 1]) {
45 ptr[j] = ptr[j - 1];
46 j--;
47 }
48
49
50
51
52 ptr[j] = temp;
53 }
54}
◆ main()
Main function.
- Returns
- 0 on exit
159 {
162 return 0;
163}
static void test()
Function to test code using random arrays.
Definition merge_insertion_sort.cpp:132
◆ 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 |
67 {
68 size_t firstIndex =
min;
69 size_t secondIndex = mid + 1;
70
71 auto ptr = array->
data();
73
74
75 for (
size_t index = min; index <=
max; index++) {
76
77 if (firstIndex <= mid &&
78 (secondIndex > max || ptr[firstIndex] <= ptr[secondIndex])) {
79 tempArray[index] = ptr[firstIndex];
80 firstIndex++;
81 } else {
82 tempArray[index] = ptr[secondIndex];
83 secondIndex++;
84 }
85 }
86
87
88 memcpy(ptr + min, tempArray.data() + min, (max - min) *
sizeof(T));
89
90
91}
◆ 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 |
108 {
109
110 if ((max - min) <= threshold) {
112 } else {
113
114 size_t mid = (
max +
min) >> 1;
115
116
119
120
121 merge(array, min, max, mid);
122 }
123}
void merge(int *arr, int l, int m, int r)
Definition merge_sort.cpp:33
void mergeSort(int *arr, int l, int r)
Definition merge_sort.cpp:71
static void InsertionSort(std::array< T, N > *A, size_t start, size_t end)
Insertion merge algorithm.
Definition merge_insertion_sort.cpp:37
◆ test()
Function to test code using random arrays.
- Returns
- none
132 {
133 constexpr size_t size = 30;
135
136 for (int i = 0; i < size; i++) {
139 }
141
143
144
145
146 for (int i = 0; i < size; ++i) {
148 }
150
153}