Merge sort implementation in C ++

Last Updated On Sunday 5th Sep 2021

Creating dynamically sized arrays at runtime is done with std::vector<T>.

  • Ideally, you would get your input using one of these.
  • If not, then they are easy to convert.
  • For example, you can create two arrays like this
	template <typename T>
void merge_sort(std::vector<T>& array) {
    if (1 < array.size()) {
        std::vector<T> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        std::vector<T> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}

	
  • However, Allocating dynamic arrays is relatively slow and should generally be avoided whenever possible.

  • For a merge sort, you can sort the subsequences of the original array and merge instead.

  • Seems like std::inplace_merge() asking for bidirectional iterators.