main.cpp

合并排序的改进方法。当数字少到一个程度的时候

#include <iostream>
using namespace std;
void mergeSort(int A[], int p, int r);
void merge(int A[], int p, int q, int r);
void insertionSort(int A[],int p, int r);


int main()
{
	  int input[] = {5, 2, 4, 6,1, 3, 2, 6};
	  int i ;

	//by default, merge sort is excuted
	mergeSort(input,0,7);
	
	cout <<"finished" <<endl;
	
	for (int i=0; i<(sizeof(input) / sizeof(int)); i++)
	{
		cout << input[i] <<endl;
	}
	
	cin >> i;

	return 0;
}

 void mergeSort(int A[], int l, int r) {

	//to check if the input array reaches a certain seize 
	//and swith to the insertion sort

	
	/*if (r - p + 1 <= 5)
	{
		insertionSort(A,p,r);
	}*/
	/*else
	{*/
	 if(l < r)
	 {
		 //the middle number that used to divided into 2 parts of the array 		
		 int m = (l + r) / 2;
		 //cout << q <<endl;		
		 //cout << "l = " <<l <<" r = "<<r<<endl;
		 mergeSort(A, l, m);
		
		 mergeSort(A, m + 1, r);
		 merge(A, l, m, r);		
	 }
	/*}*/
}

void merge(int A[], int l, int m, int r) {
    
	//cout << "l = "<<l <<" m = "<<m<<" r = "<<r<<endl;
	int i, j, k, size;
    int* B;
	
    
    
    //the size of the new array
	size = r - l + 1;
	
	//temp arry for storing the merge result
    B = new int[size];


    
    //initialize B
    for (int i = 0; i < size; ++i) {
        B[i] = 0;
    }

    i = l;
    j = m + 1;
    k = 0;
    
    //compare and copy the smaller to B
    while (i <= m && j <= r) {
        if (A[i] < A[j]) {
            B[k++] = A[i++];
        } else {
            B[k++] = A[j++];
        }
    }
    
    //copy the rest to B
    while (i <= m) {
        B[k++] = A[i++];
    }    
    while (j <= r) {
        B[k++] = A[j++];
    }
    
    //replace A[p..r] with B[0..r-p]
    for (i = l, k = 0; i <= r; ++i, ++k) {
        A[i] = B[k];
    }

    delete[] B;
}

void insertionSort(int A[],int p, int r)
{
	int size = r - p + 1;
	
	for (int p=1; p < size; p++)
	{
		int tmp = A[p];
		int j;
		for(j = p; j > 0 && tmp < A[j-1]; j--)
			//if the condition is true, swap A[j] and A[j-1]
			A[j] = A[j-1];
		A[j] = tmp;
	}
}