快速排序则达到了这种平衡，并且是C++库中通常所使用的排序算法。在Java中，快速排序也用作基本类型的标准库排序。

代码实现

// C++
void mergeSort(int a[], int length, int left, int right) {  // 归并排序(递归版)，启动时left = 0，right = length- 1
	int mid = left + (right - left) / 2;  // 中间(分割)位置 
	if (left < right) {  // 递归出口 
		mergeSort(a, length, left, mid);  // 递归排序左序列 
		mergeSort(a, length, mid + 1, right);  // 递归排序右序列
		merge(a, left, mid, right);  // 合并左右子序列 
	}
}
void merge(int a[], int left, int mid, int right) {  // 合并左右子序列 
	int n1 = mid - left + 1;  // 左序列元素个数 
	int n2 = right - mid;  // 右序列元素个数 
	int L[n1 + 1];  // 左辅助数组 
	int R[n2 + 1];  // 右辅助数组 
	
	for (int i = 0; i < n1; i++) {  // 初始化左辅助数组
		L[i] = a[left + i];
	}
	for (int i = 0; i < n2; i++) {  // 初始化右辅助数组
		R[i] = a[mid + i + 1];
	}
	
	// 哨兵，用于合并时的边界判断 
	const int INF = 0x7fffffff;  // 32字节int最大值 
	L[n1] = INF;  // 以无穷大(32字节int最大值)为数组结束标志 
	R[n2] = INF;  // 以无穷大(32字节int最大值)为数组结束标志
	
 	int i = 0;  // L数组指针 
 	int j = 0;  // R数组指针 
	for (int k = left; k <= right; k++) {  // 每次选取两数组中较小者 
		if (L[i] <= R[j]) {  // L[i] <= R[j]
			a[k] = L[i];  // L[i]填入 
			i++;  // L数组指针后移 
		} else {  // L[i] > R[j] 
			a[k] = R[j];  // R[j]填入 
			j++;  // R数组指针后移 
		}
	}
}

// Java
class MergeSort {
    // 归并排序驱动程序1(全排序)
    public void mergeSort(int[] array) {
        mergesort(array, 0, array.length - 1);  // 调用私有方法排序
    }
    // 归并排序驱动程序2(部分排序)
    public void mergeSort(int[] array, int left, int right) {
        mergesort(array, left, right);  // 调用私有方法排序
    }
    private void mergesort(int[] array, int left, int right) {
        if (left < right) {  // 递归出口
            int mid = left + (right - left) / 2;  // 中间(分割)位置
            mergesort(array, left, mid);  // 递归排序左序列
            mergesort(array, mid + 1, right);  // 递归排序右序列
            merge(array, left, mid, right);  // 合并左右子序列
        }
    }
    // 合并左右子序列
    private void merge(int[] array, int left, int mid, int right) {
        int leftlength = mid - left + 1;  // 左序列元素个数
        int rightlength = right - mid;  // 右序列元素个数
        int[] arrayL = new int[leftlength + 1];  // 左辅助数组
        int[] arrayR = new int[rightlength + 1];  // 右辅助数组

        for (int i = 0; i < leftlength; ++i) {  // 初始化左辅助数组
            arrayL[i] = array[left + i];
        }
        arrayL[leftlength] = Integer.MAX_VALUE;// 哨兵，用于合并时的边界判断
        for (int i = 0; i < rightlength; ++i) {  // 初始化右辅助数组
            arrayR[i] = array[mid + i + 1];
        }
        arrayR[rightlength] = Integer.MAX_VALUE;// 哨兵，用于合并时的边界判断

        int i = 0;  // L数组指针
        int j = 0;  // R数组指针
        for (int k = left; k <= right; ++k) {  // 每次选取两数组中较小者
            if (arrayL[i] <= arrayR[j]) {
                array[k] = arrayL[i++];  // 填入较小者，指针后移
            } else {
                array[k] = arrayR[j++];  // 填入较小者，指针后移
            }
        }
    }
}

参考

算法导论

数据结构与算法分析(Java语言描述)

数据结构(C语言版)