// a compilation time version of the merge sort algorithm /* implemented algorithm: a[n] = [i, j, ...] arrays=split a -> a[i], a[j], ... while size of arrays > 1 s=size of arrays i=0..s/2 fuse array[2*i] and arrat[2*i+1] fuse algorithm merge two sorted arrays to obtain a sorted array */ #include using std::cout; using std::endl; // Array class, helper that "store" our integers template struct Array{}; // Type class, helper for ::type template struct Type{ using type = T; }; // --- If class on type // declaration template struct IfType; // specialisation with B == true so type == T template struct IfType : Type {}; // specialisation with B == false so type == V template struct IfType : Type {}; // Helper to call IfType<...>::type easily template using If_t = typename IfType::type; // --- Merge class // declaration template struct Merge; // starting point with two arrays with one value each // compare first int of each array, merge them in the right order template struct Merge, Array> : IfType< (I < J), Array, Array > {}; // starting point with two arrays with more than one value each // compare first int of each array, store the lower in third Array and remove it from its array, then go to generic step template struct Merge, Array> : IfType<(I < J), typename Merge, Array, Array>::type, typename Merge, Array, Array>::type > {}; // starting point with two arrays, one with more than one value, one with one // compare first int of each array, store the lower in third Array and remove it from its array, then go to generic step. If the lower value is in the array with only one value, we stop the "recursion" template struct Merge, Array> : IfType<(I < J), Array, typename Merge, Array, Array>::type > {}; // starting point with two arrays, one with more than one value, one with one // compare first int of each array, store the lower in third Array and remove it from its array, then go to generic step. If the lower value is in the array with only one value, we stop the "recursion" template struct Merge, Array> : IfType<(I < J), typename Merge, Array, Array>::type, Array > {}; // "recursion" step with two arrays with more than one value each // compare first int of each array, store the lower in third Array and remove it from its array, then go again to generic step template struct Merge, Array, Array> : IfType<(I < J), typename Merge, Array, Array>::type, typename Merge, Array, Array>::type > {}; // "recursion" step with two arrays, one with more than one value, one with one // compare first int of each array, store the lower in third Array and remove it from its array, then go again to generic step. If the lower value is in the array with only one value, we stop the "recursion" template struct Merge, Array, Array> : IfType<(I < J), Array, typename Merge, Array, Array>::type > {}; // "recursion" step with two arrays, one with more than one value, one with one // compare first int of each array, store the lower in third Array and remove it from its array, then go again to generic step. If the lower value is in the array with only one value, we stop the "recursion" template struct Merge, Array, Array> : IfType<(I < J), typename Merge, Array, Array>::type, Array > {}; // end point with two arrays containing one value each. Store them in the right order in Result then end "recursion" template struct Merge, Array, Array> : IfType<(I < J), Array, Array > {}; // Helper to make the use of Merge class easier template using Merge_t = typename Merge::type; // --- ArrayOfArray class template struct ArrayOfArray{}; // --- Result class // declaration template struct Result; // "recursion" step, print an integer then call show of the parent class template struct Result : Result{ void show(){ cout << J << ' '; Result::show(); } }; // "recursion stop", print the integer template struct Result{ void show(){ cout << I << endl; } }; // --- MergeSortImpl // declaration template struct MergeSortImpl; // 1. case with only one value: already sorted template struct MergeSortImpl> : Result {}; // 2. case with two value: they are just put in the right order template struct MergeSortImpl, Array> : If_t< (I < J), Result, Result > {}; // 3. starting point with more than one value (as the behavior with only one is already defined): we split the array intoarrays of size one thanks to pack expansion template struct MergeSortImpl> : MergeSortImpl...> {}; // 4. case with more than two arrays: we merge the two first and put the result into an array of array, then go to step 7., 8. or 9. depending on the number of arrays in T... template struct MergeSortImpl, Array, T...> : MergeSortImpl< ArrayOfArray< Merge_t< Array, Array > >, T... > {}; // 5. case with an array of array containing only one array and no array outside of it: this array is the result template typename T> struct MergeSortImpl< ArrayOfArray> > : Result {}; // 6. case with an array of array containing more than one array but no array outside of it: we remove the array of array, only keeping arrays inside of it and go to step 4. template struct MergeSortImpl< ArrayOfArray > : MergeSortImpl {}; // 7. case with an array of array and one array outside of it, we remove the array of array keeping what is inside and go to step 4. template struct MergeSortImpl< ArrayOfArray, Array > : MergeSortImpl> {}; // 8. case with an array of array and two arrays outside of it, we remove the array of array keeping what is inside, we merge the two arrays that were outside of it and go to step 4. template struct MergeSortImpl< ArrayOfArray, Array, Array > : MergeSortImpl< T..., Merge_t< Array, Array > > {}; // 9. case with an array of array and more than two arrays outside of it, we merge the two first arrays from those outside of the array of arrays, put the result inside it and go again to step 9. template struct MergeSortImpl< ArrayOfArray, Array, Array, U... > : MergeSortImpl< ArrayOfArray< T..., Merge_t< Array, Array > >, U... > {}; // --- MergeSort, helper to call MergeSortImpl easily template using MergeSort = MergeSortImpl>; // --- Test Display class template struct TestDisplay{ static void run(){ cout << "Unsorted array:" << endl << " "; Result().show(); cout << "Sorted:" << endl << " "; MergeSort().show(); cout << endl; } }; int main() { TestDisplay<3, 2, 1>::run(); TestDisplay<1>::run(); TestDisplay<2, 1>::run(); TestDisplay<1, 2, 3, 4>::run(); TestDisplay<1, 3, 2, 5, 7 ,6, -1>::run(); return 0; }

compile time merge sort