# Merge sort O(1) extra space

## 概念
利用某個數 /MOD 與 %MOD 結果會不一樣且可控制的特性，可以讓陣列中的一個位置同時攜帶"原本數字"與"排序後結果"兩種資訊，並分別使用"/" 與"%"提取資訊
(MOD是除數，必須要大過待排序數字中的最大值)
->如此一來便可以在不使用額外陣列的情況下完成merge動作

例子在程式碼註解中
## 程式碼(C++)

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MOD 2147483648
typedef unsigned long long int llt;
void Merge(vector<llt>& a,int Front,int mid,int End)
{
    // since number/MOD and number%MOD can be different number and they are independent
    // we can let an element of array contain both original value and sorted value
    // for example:
    // a=[3,4,6,1,2,5], Front=0,mid=2,End=5;[3,4,6],[1,2,5] has been sorted
    // in the end,a[0] shound be 1,so we temporary set a[0] to 2147483651,so that
    // a[0]/MOD=1,contain the sorted value
    // a[0]%MOD=3,contain the origin value

    int ptr1=Front,ptr2=mid+1; // the same as general merge sort
    int ans_ptr=Front; // remember what position to put the sorted value in

    while(1)
    {
        if(ptr1>mid || ptr2>End)
        {
            break;
        }
        if((a[ptr1]%MOD)<=(a[ptr2]%MOD))
        {
            a[ans_ptr]=a[ans_ptr]+(a[ptr1]%MOD)*MOD;
            ptr1++;
            ans_ptr++;
        }
        else if((a[ptr1]%MOD)>(a[ptr2]%MOD))
        {
            a[ans_ptr]=a[ans_ptr]+(a[ptr2]%MOD)*MOD;
            ptr2++;
            ans_ptr++;
        }
    }

    while(ptr1<=mid)
    {
        a[ans_ptr]=a[ans_ptr]+(a[ptr1]%MOD)*MOD;
        ptr1++;
        ans_ptr++;
    }
    while(ptr2<=End)
    {
        a[ans_ptr]=a[ans_ptr]+(a[ptr2]%MOD)*MOD;
        ptr2++;
        ans_ptr++;
    }
    for(int i=Front;i<=End;i++) //set to sorted value
    {
        a[i]=a[i]/MOD;
    }
}
void Merge_Sort(vector<llt>& a,int Front,int End)
{
    if(Front>=End)
    {
        return;
    }
    else
    {
        int mid=(Front+End)/2;
        Merge_Sort(a,Front,mid);
        Merge_Sort(a,mid+1,End);
        Merge(a,Front,mid,End);
    }
}
int main()
{
    //this progrem can deal with number range[0,2147483647];
    //the only input is to deside how many numbers should be sorted
    default_random_engine generator(time(0));
    uniform_int_distribution<int> distribution(0,2147483647);
    int n;
    int input;
    int random;
    vector<llt> a;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        random=distribution(generator);
        a.push_back(random);
    }
    Merge_Sort(a,0,n-1);
    for(auto x:a)
    {
        cout<<x<<" ";
    }
}