#include <iostream>
#include <vector>
template < class T>
void merge( std:: vector < T> & v, int p, int q, int r)
{
int size1 = q- p+ 1 ;
int size2 = r- q;
std:: vector < T> L( size1) ;
std:: vector < T> R( size2) ;
for ( int i = 0 ; i < size1; i++ )
{
L[ i] = v[ p+ i] ;
}
for ( int j = 0 ; j < size2; j++ )
{
R[ j] = v[ q+ j+ 1 ] ;
}
int i= 0 ,j= 0 ;
int k;
for ( k = p; k <= r && i < size1 && j < size2; k++ )
{
if ( L[ i] <= R[ j] )
{
v[ k] = L[ i] ;
i++ ;
}
else
{
v[ k] = R[ j] ;
j++ ;
}
}
for ( i = i; i < size1; ++ i)
{
v[ k] = L[ i] ;
k++ ;
}
for ( j = j; j < size2; j++ )
{
v[ k] = R[ j] ;
k++ ;
}
}
template < class T>
void merge_sort( std:: vector < T> & v, int p, int r) {
if ( p < r)
{
int q = ( p+ r) / 2 ;
merge_sort( v, p, q) ;
merge_sort( v, q+ 1 , r) ;
merge( v, p, q, r) ;
}
}
int main( )
{
std:: vector < int > vec;
vec.push_back ( 13 ) ;
vec.push_back ( 5 ) ;
vec.push_back ( 7 ) ;
vec.push_back ( 7 ) ;
vec.push_back ( 4 ) ;
vec.push_back ( 2 ) ;
vec.push_back ( 10 ) ;
int sz = vec.size ( ) ;
std:: cout << "Entered array : " ;
for ( int n = 0 ; n < sz; n++ ) {
std:: cout << vec[ n] << " " ;
}
std:: cout << "\n " ;
std:: cout << "Sorted array : " ;
merge_sort( vec, 0 , sz- 1 ) ;
for ( int n = 0 ; n < sz; n++ ) {
std:: cout << vec[ n] << " " ;
}
std:: cout << "\n " ;
std:: vector < char > c;
c.push_back ( 'd' ) ;
c.push_back ( 'y' ) ;
c.push_back ( 'h' ) ;
c.push_back ( 'l' ) ;
c.push_back ( 'e' ) ;
c.push_back ( 'a' ) ;
int sz1 = c.size ( ) ;
std:: cout << "Entered array : " ;
for ( int n = 0 ; n < sz1; n++ ) {
std:: cout << c[ n] << " " ;
}
std:: cout << "\n " ;
std:: cout << "Sorted array : " ;
merge_sort( c, 0 , sz1- 1 ) ;
for ( int n = 0 ; n < sz1; n++ ) {
std:: cout << c[ n] << " " ;
}
std:: cout << "\n " ;
std:: vector < std:: string > str;
str.push_back ( "car" ) ;
str.push_back ( "dog" ) ;
str.push_back ( "apple" ) ;
str.push_back ( "ball" ) ;
str.push_back ( "tree" ) ;
int sz2 = str.size ( ) ;
std:: cout << "Entered array : " ;
for ( int n = 0 ; n < sz2; n++ ) {
std:: cout << str[ n] << " " ;
}
std:: cout << "\n " ;
std:: cout << "Sorted array : " ;
merge_sort( str, 0 , sz2- 1 ) ;
for ( int n = 0 ; n < sz2; n++ ) {
std:: cout << str[ n] << " " ;
}
std:: cout << "\n " ;
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKCnRlbXBsYXRlPGNsYXNzIFQ+CnZvaWQgbWVyZ2Uoc3RkOjp2ZWN0b3I8VD4mIHYsIGludCBwLCBpbnQgcSwgaW50IHIpCnsKaW50IHNpemUxID0gcS1wKzE7CmludCBzaXplMiA9IHItcTsKc3RkOjp2ZWN0b3I8VD4gTChzaXplMSk7CnN0ZDo6dmVjdG9yPFQ+IFIoc2l6ZTIpOwoKZm9yKGludCBpID0gMDsgaSA8IHNpemUxOyBpKyspCnsKICAgIExbaV0gPSB2W3AraV07Cn0KZm9yKGludCBqID0gMDsgaiA8IHNpemUyOyBqKyspCnsKICAgIFJbal09dltxK2orMV07Cn0KCmludCBpPTAsaj0wOwppbnQgazsKZm9yKGsgPSBwOyBrIDw9IHIgJiYgaSA8IHNpemUxICYmIGogPCBzaXplMjsgaysrKQp7CiAgICBpZihMW2ldIDw9IFJbal0pCiAgICB7CiAgICAgICAgdltrXSA9IExbaV07CiAgICAgICAgaSsrOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHZba10gPSBSW2pdOwogICAgICAgIGorKzsKICAgIH0KfQpmb3IoaSA9IGk7IGkgPCBzaXplMTsgKytpKQp7CiAgICB2W2tdID0gTFtpXTsKICAgIGsrKzsKfQoKZm9yKGogPSBqOyBqIDwgc2l6ZTI7IGorKykKICAgIHsKICAgICAgICB2W2tdID0gUltqXTsKICAgICAgICBrKys7CiAgICB9Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+CnZvaWQgbWVyZ2Vfc29ydChzdGQ6OnZlY3RvcjxUPiYgdiwgaW50IHAsIGludCByKXsKaWYocCA8IHIpCnsKICAgIGludCBxID0gKHArcikvMjsKICAgIG1lcmdlX3NvcnQodiwgcCwgcSk7CiAgICBtZXJnZV9zb3J0KHYsIHErMSwgcik7CiAgICBtZXJnZSh2LCBwLCBxLCByKTsKfQp9CgppbnQgbWFpbigpCnsKc3RkOjp2ZWN0b3I8aW50PnZlYzsKdmVjLnB1c2hfYmFjaygxMyk7CnZlYy5wdXNoX2JhY2soNSk7CnZlYy5wdXNoX2JhY2soNyk7CnZlYy5wdXNoX2JhY2soNyk7CnZlYy5wdXNoX2JhY2soNCk7CnZlYy5wdXNoX2JhY2soMik7CnZlYy5wdXNoX2JhY2soMTApOwppbnQgc3ogPSB2ZWMuc2l6ZSgpOwpzdGQ6OmNvdXQgPDwgIkVudGVyZWQgYXJyYXkgOiAiOwpmb3IoaW50IG4gPSAwOyBuIDwgc3o7IG4rKyl7CiAgICBzdGQ6OmNvdXQgPDwgdmVjW25dIDw8IiAiOwp9CnN0ZDo6Y291dCA8PCAiXG4iOwpzdGQ6OmNvdXQgPDwgIlNvcnRlZCBhcnJheSA6ICI7Cm1lcmdlX3NvcnQodmVjLCAwLCBzei0xKTsKZm9yKGludCBuID0gMDsgbiA8IHN6OyBuKyspewogICAgc3RkOjpjb3V0IDw8IHZlY1tuXSA8PCAiICI7Cn0Kc3RkOjpjb3V0IDw8ICJcbiI7CgpzdGQ6OnZlY3RvcjxjaGFyPiBjOwpjLnB1c2hfYmFjaygnZCcpOwpjLnB1c2hfYmFjaygneScpOwpjLnB1c2hfYmFjaygnaCcpOwpjLnB1c2hfYmFjaygnbCcpOwpjLnB1c2hfYmFjaygnZScpOwpjLnB1c2hfYmFjaygnYScpOwppbnQgc3oxID0gYy5zaXplKCk7CnN0ZDo6Y291dCA8PCAiRW50ZXJlZCBhcnJheSA6ICI7CmZvcihpbnQgbiA9IDA7IG4gPCBzejE7IG4rKyl7CiAgICBzdGQ6OmNvdXQgPDwgY1tuXSA8PCIgIjsKfQpzdGQ6OmNvdXQgPDwgIlxuIjsKc3RkOjpjb3V0IDw8ICJTb3J0ZWQgYXJyYXkgOiAiOwptZXJnZV9zb3J0KGMsIDAsIHN6MS0xKTsKZm9yKGludCBuID0gMDsgbiA8IHN6MTsgbisrKXsKICAgIHN0ZDo6Y291dCA8PCBjW25dIDw8ICIgIjsKfQpzdGQ6OmNvdXQgPDwgIlxuIjsKCnN0ZDo6dmVjdG9yPHN0ZDo6c3RyaW5nPiBzdHI7CnN0ci5wdXNoX2JhY2soImNhciIpOwpzdHIucHVzaF9iYWNrKCJkb2ciKTsKc3RyLnB1c2hfYmFjaygiYXBwbGUiKTsKc3RyLnB1c2hfYmFjaygiYmFsbCIpOwpzdHIucHVzaF9iYWNrKCJ0cmVlIik7CmludCBzejIgPSBzdHIuc2l6ZSgpOwoKc3RkOjpjb3V0IDw8ICJFbnRlcmVkIGFycmF5IDogIjsKZm9yKGludCBuID0gMDsgbiA8IHN6MjsgbisrKXsKICAgIHN0ZDo6Y291dCA8PCBzdHJbbl0gPDwiICI7Cn0Kc3RkOjpjb3V0IDw8ICJcbiI7CnN0ZDo6Y291dCA8PCAiU29ydGVkIGFycmF5IDogIjsKbWVyZ2Vfc29ydChzdHIsIDAsIHN6Mi0xKTsKZm9yKGludCBuID0gMDsgbiA8IHN6MjsgbisrKXsKICAgIHN0ZDo6Y291dCA8PCBzdHJbbl0gPDwgIiAiOwp9CnN0ZDo6Y291dCA8PCAiXG4iOwoKICAgIHJldHVybiAwOwp9Cg==