[impersonalis]

Комбинированный метод

Для больших массивов ( или, при рекурсивном вызове, частей массивов) используем буыструю сортировку, для частей с длиной меньше параметра (M) - сортировку пузырьком.

Примерно так:

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

void B_Sort(int a[],long N){
	int temp;
	for(int j=1;j<N;j++){
 for(int i=0;i<N-j;i++){
 	if(a[i]>a[i+1]){
  temp=a[i];
  a[i]=a[i+1];
  a[i+1]=temp;
 	}
 }
	}
}

void Quick_Sort(int a[], long N,int M) {
	long left=0, right=N-1; 
	int temp;
	int c=a[ N>>1 ];
	do {
 while ( a[left] < c ) left++;
 while ( a[right] > c ) right--;

 if (left <= right) {
 	temp = a[left]; 
 	a[left] = a[right]; 
 	a[right] = temp;
 	left++;
 	right--;
 }
	} while ( left<=right );

	if ( right > 0 ){
 if (right>=M)
 	Quick_Sort(a, right,M);
 else
 	B_Sort(a,right);
	}
	if ( N > left ){
 if (N-left>=M)
 	Quick_Sort(a+left, N-left,M);
 else
 	B_Sort(a+left, N-left);
	}
}



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