###Merge sort
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void merge(vector<int>& array,int left,int pivot,int right){
int leftLen = pivot - left + 1;
int rightLen = right - pivot;
vector<int> L(leftLen);
vector<int> R(rightLen);
int i,j;
for(i = 0; i < leftLen; ++i){
L[i] = array[left + i];
}
for(j = 0; j < rightLen; ++j){
R[j] = array[pivot + 1 + j];
}
int k = left;
for(i = 0,j = 0; i < leftLen && j < rightLen; ++k){
if(L[i] < R[j]){
array[k] = L[i++];
}else{
array[k] = R[j++];
}
}
if(i < leftLen){
for(; i < leftLen; ++i,++k){
array[k] = L[i];
}
}
if(j < rightLen){
for(; j < rightLen; ++k,++j){
array[k] = R[j];
}
}
}
void merge_sort(vector<int>& array,int left,int right){
if(left < right){
int q = left + ((right - left)>>1);
merge_sort(array,left,q);
merge_sort(array,q+1,right);
merge(array,left,q,right);
}
}
void print(vector<int>& array){
for(int i = 0; i < array.size(); ++i){
cout<<array[i]<<" ";
}
cout<<endl;
}
int main(){
vector<int> Test;
for(int i = 0; i < 20; ++i){
Test.push_back(i);
}
random_shuffle(Test.begin(),Test.end());
print(Test);
merge_sort(Test,0,Test.size() - 1);
print(Test);
system("pause");
return 0;
}