[impersonalis]

Центрированная вставка
Видел несколько схожих описаний алгоритма. По сути: работа с массивом как с бинарным древом поиска, но при этом гибкость, получаемая при реализации связанным списком, отсутствует - так что код громоздкий и медленный (по сравнению с возможным: скорость падает на сдвигах эл-тов и завершающем копировании, но экономится время при поиске места). Вероятно, рассчитан на специфические входные данные.

#include<iostream.h>
#include<conio.h>

void sort(int m[],int n){
	cout<<"start function!"<<endl;
	int *b=new int[n];//
	int c=n*0.5;//
	int left_ptr=0;//
	int right_ptr=c+1;//
	b[c]=m[0];//
	cout<<"Value of a median "<<b[c]<<";On a position="<<c<<endl;
	cout<<"--"<<endl;
	for(int i=1;i<n;i++){//
 *cout<<endl<<"analysis of value "<<m[i]<<";On a position="<<i<<endl;
 *if(m[i]<b[c]){
 *	cout<<"Choice of the left branch"<<endl;
 *	//++++
 *	if(left_ptr==c){
 * *cout<<"left branch is loaded - displacement elements"<<endl;
 * *for(int j=right_ptr;j>left_ptr;j--){//+1
 * *	b[j]=b[j-1];
 * *}
 * *c++;
 * *left_ptr++;
 *	}
 *	for(int j=0;j<=left_ptr;j++){
 * *//@
 * *if(m[i]<b[j]){
 * *	cout<<"The place of an analyzed element is not empty - displacement of elements"<<endl;
 * *	for(int j2=left_ptr;j2>j;j2--){//+1
 * * *b[j2]=b[j2-1];
 * *	}
 * *	left_ptr++;
 * *	b[j]=m[i];
 * *	break;
 * *}
 * *//@
 * *if(j==left_ptr){
 * *	cout<<"Are analyzed an element has taken a place at the end of a branch"<<endl;
 * *	left_ptr++;
 * *	b[j]=m[i];
 * *	break;
 * *}
 *	}
 *	//++++
 *}
 *////////////////////
 *else{
 *	cout<<"Choice of the right branch"<<endl;
 *	//++++
 *	if(right_ptr==n){
 * *cout<<"right branch is loaded - displacement elements"<<endl;
 * *for(int j=left_ptr;j<right_ptr;j++){//-1
 * *	b[j]=b[j+1];
 * *}
 * *c--;
 * *right_ptr--;
 *	}
 *	for(int j=0;j<=right_ptr;j++){
 * *//@
 * *if(m[i]<b[j]){
 * *	cout<<"The place of an analyzed element is not empty - displacement of elements"<<endl;
 * *	for(int j2=right_ptr;j2>j;j2--){//+1
 * * *b[j2]=b[j2-1];
 * *	}
 * *	right_ptr++;
 * *	b[j]=m[i];
 * *	break;
 * *}
 * *//@
 * *if(j==right_ptr){
 * *	cout<<"Are analyzed an element has taken a place at the end of a branch"<<endl;
 * *	right_ptr++;
 * *	b[j]=m[i];
 * *	break;
 * *}
 *	}
 *	//+++++
 *}
 *////////////////////////
 *cout<<"array: ";
 *for(int ii=0;ii<n;ii++)
 *	cout<<b[ii]<<";";
 *cout<<endl;
	
	}
	cout<<"copy..."<<endl;
	for(int j=0;j<n;j++){
	m[j]=b[j];
	}
	cout<<"end function!"<<endl;
}

void main(){
	int n;
	cin>>n;
	int *m=new int[n];
	int i;
	for( i=0;i<n;i++){
 *cin>>m[i];
	}
	sort(m,n);
	cout<<"**"<<endl;
for(i=0;i<n;i++){
 *cout<<m[i]<<endl;
	}
	getch();
}