merge sort ascending c++ code example
Example 1: merge sort
function merge(list, start, midpoint, end) {
const left = list.slice(start, midpoint);
const right = list.slice(midpoint, end);
for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
if (topLeft >= left.length) {
list[i] = right[topRight++];
} else if (topRight >= right.length) {
list[i] = left[topLeft++];
} else if (left[topLeft] < right[topRight]) {
list[i] = left[topLeft++];
} else {
list[i] = right[topRight++];
}
}
}
function mergesort(list, start = 0, end = undefined) {
if (end === undefined) {
end = list.length;
}
if (end - start > 1) {
const midpoint = ((end + start) / 2) >> 0;
mergesort(list, start, midpoint);
mergesort(list, midpoint, end);
merge(list, start, midpoint, end);
}
return list;
}
mergesort([4, 7, 2, 6, 4, 1, 8, 3]);
Example 2: merge sort c++
#include "tools.hpp"
std::vector<int> sort(size_t start, size_t length, const std::vector<int>& vec)
{
if(vec.size()==0 ||vec.size() == 1)
return vec;
vector<int> left,right;
size_t mid_point = vec.size()/2;
for(int i = 0 ; i < mid_point; ++i){left.emplace_back(vec[i]);}
for(int j = mid_point; j < length; ++j){ right.emplace_back(vec[j]);}
left = sort(start,mid_point,left);
right = sort(mid_point,length-mid_point,right);
return merge(left,right);
}
vector<int> merge(const vector<int>& a, const vector<int>& b)
{
vector<int> merged_a_b(a.size()+b.size(),0);
int i = 0;
int j = 0;
int k = 0;
int left_size = a.size();
int right_size = b.size();
while(i<left_size && j<right_size)
{
if(a[i]<b[j])
{
merged_a_b[k]=a[i];
i++;
}
else
{
merged_a_b[k]=b[j];
j++;
}
k++;
}
while(i<left_size)
{
merged_a_b[k]=a[i];
i++;
k++;
}
while(j<right_size)
{
merged_a_b[k]=b[j];
j++;
k++;
}
return merged_a_b;
}