1.归并排序（非递归）

public void mergeSort(int arr[]) {

　　int size = arr.length;

　　int mergeSize = 1;

　　while(mergeSize < size) {

　　　　int L = 0;

　　　　while(L < size) {

　　　　　　int M = L + mergeSize - 1;

　　　　　　if(M >= size) {

　　　　　　　　break;

　　　　　　}

　　　　　　int R = Math.min(size - 1,M + mergeSize);

　　　　　　merge(arr,L,M,R);

　　　　　　L = R + 1;

　　　　}

　　　　if(mergeSize > size / 2) {

　　　　　　break;

　　　　}

　　　　mergeSize <<= 1;

　　}

}

public void merge(int arr[],int left,int mid,int right) {

　　int s1 = left;

　　int s2 = mid + 1;

　　int i = 0;

　　int temp = new int[right - left + 1];

　　while(s1 <= mid && s2 <= right) {

　　　　if(arr[s1] <= arr[s2]) {

　　　　　　temp[i ++] = arr[s1 ++];

　　　　}else {

　　　　　　temp[i ++] = arr[s2 ++];

　　　　}

　　}

　　while(s1 <= mid) {

　　　　temp[i ++] = arr[s1 ++];

　　}

　　while(s2 <= right) {

　　　　temp[i ++] = arr[s2 ++];

　　}

　　for(int j = 0;j < temp.length;j ++) {

　　　　arr[low + j] = temp[j];

　　}

}

2.求数组中的每个数左边比他小的数的和的总和

public class MergeSort {
　　int res = 0;
　　public int mergeSort(int arr[],int low,int height) {
　　　　int size = arr.length;
　　　　int mergeSize = 1;
　　　　while(mergeSize < size) {
　　　　　　int L = 0;
　　　　　　while(L < size) {
　　　　　　　　int M = L + mergeSize - 1;
　　　　　　　　if(M >= size) {
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　int R = Math.min(size - 1,M + mergeSize);
　　　　　　　　merge(arr,L,M,R);
　　　　　　　　L = R + 1;
　　　　　　}
　　　　　　if(mergeSize > size / 2) {
　　　　　　　　break;
　　　　　　}
　　　　　　mergeSize <<= 1;
　　　　}
　　　　return res;
　　}
　　public void merge(int arr[],int low,int mid,int height) {
　　　　int s1 = low;
　　　　int s2 = mid + 1;
　　　　int temp[] = new int[height - low + 1];
　　　　int i = 0;
　　　　while(s1 <= mid && s2 <= height) {
　　　　　　if(arr[s1] < arr[s2]) {　　　　　　　　//若左右相同，一定要先入右边
　　　　　　　　res += arr[s1] * (height - s2 + 1);
　　　　　　　　temp[i ++] = arr[s1 ++];
　　　　　　}else {
　　　　　　　　temp[i ++] = arr[s2 ++];
　　　　　　}
　　　　}
　　　　while(s1 <= mid) {
　　　　　　temp[i ++] = arr[s1 ++];
　　　　}
　　　　while(s2 <= height) {
　　　　　　temp[i ++] = arr[s2 ++];
　　　　}
　　　　for(int j = 0;j < temp.length;j ++){
　　　　　　arr[low + j] = temp[j];
　　　　}
　　}
}