#include <iostream>
#include <ctime>
using namespace std;
const int MaxArraySize = 16374;
#ifdef RAND_MAX
#undef RAND_MAX
#define RAND_MAX 1000000
#endif
template <class T>
void bubble_sort(T* array, int s) ...{
bool exchange = true;
int i;
while(exchange) ...{
exchange = false;
for(i = 0; i < s - 1; i++) ...{
if(array[i] > array[i+1]) ...{
T t = array[i];
array[i] = array[i+1];
array[i+1] = t;
exchange = true;
}
}
}
}
template <class T>
void bubble_sort_bound(T* array, int s) ...{
int bound = s - 1, i, t;
while(bound) ...{
t = 0;
for(i = 0; i < bound; i++) ...{
if(array[i] > array[i+1]) ...{
T temp = array[i]; array[i] = array[i+1]; array[i+1] = temp;
t = i;
}
}
bound = t;
}
}
template <class T>
void bubble_sort_bigo(T* array, int s) ...{
int first = 0, last = s-1, i, t;
T temp;
while(first < last) ...{
for(i = first, t = first; i < last; i++) ...{
if(array[i] > array[i+1]) ...{
temp = array[i]; array[i] = array[i+1]; array[i+1] = temp;
t = i;
}
}
last = t;
for(i = last, t = last; i > first; i--) ...{
if(array[i] < array[i-1]) ...{
temp = array[i]; array[i] = array[i-1]; array[i-1] = temp;
t = i;
}
}
first = t;
}
}
template <class T>
void insertion_sort(T* array, int s) ...{
int i,j;
T t;
for(i = 1; i < s; i++) ...{
t = array[i];
j = i - 1;
while(j >= 0 && array[j] > t) ...{
array[j+1] = array[j];
j--;
}
array[j+1] = t;
}
}
template <class T>
void insertion_sort_x(T* array, int s) ...{
int i, j, low, high, mid;
T t;
for(i = 1; i < s; i++) ...{
low = 0; high = i - 1; t = array[i];
while(low <= high) ...{
mid = (low + high) / 2;
if(array[mid] <= t) low = mid + 1;
else if(array[mid] >= t) high = mid - 1;
}
for(j = i - 1; j > high; j--)
array[j+1] = array[j];
array[j+1] = t;
}
}
template <class T>
void select_sort(T* array, int s) ...{
int i,j,k;
for(i = 0; i < s; i++) ...{
k = i;
for(j = i + 1; j < s; j++) ...{
if(array[j] < array[k])
k = j;
}
T t = array[i];
array[i] = array[k];
array[k] = t;
}
}
template <class T>
void merge_sort_x(T* array, int begin, int end) ...{
if(end - begin +1 <= 16) ...{
int i,j;
T t;
for(i = begin + 1; i <= end; i++) ...{
j = i - 1; t = array[i];
while(j >= begin && array[j] > t) ...{
array[j+1] = array[j];
j--;
}
array[j+1] = t;
}
return;
}
if