经典算法巡礼(五) -- 排序之归并排序

	// merge方法实现归并排序中的归并操作，将两个已排序数组归并操作成一个已排序数组
	func (this *MergeSort) merge(a []Comparable, compare Compare, lo int, mid int, hi int) {
		i := lo
		j := mid + 1

		arrayBak := make([]Comparable, len(a))
		copy(arrayBak, a)

		for k := lo; k <= hi; k++ {
			if i > mid {
				a[k] = arrayBak[j]
				j++
			} else if j > hi {
				a[k] = arrayBak[i]
				i++
			} else if this.less(arrayBak[i], arrayBak[j], compare) {
				a[k] = arrayBak[i]
				i++
			} else {
				a[k] = arrayBak[j]
				j++
			}
		}
	}

	// Sort1采用自顶向下方法进行归并排序
	// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
	func (this *MergeSort) sort1(a []Comparable, compare Compare, lo int, hi int) {
		if lo >= hi {
			return
		}

		mid := (lo + hi) / 2

		this.sort1(a, compare, lo, mid)
		this.sort1(a, compare, mid+1, hi)
		this.merge(a, compare, lo, mid, hi)
	}

	// Sort2采用自底向上方法进行归并排序，先从子数组为1开始归并操作，逐渐递增，直到归并成完整数组为止
	// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
	func (this *MergeSort) sort2(a []Comparable, compare Compare) {
		for sz := 1; sz < len(a); sz += sz {
			for lo := 0; lo < len(a)-sz; lo += sz + sz {
				this.merge(a, compare, lo, lo+sz-1, int(math.Min(float64(lo+sz+sz-1), float64(len(a)-1))))
			}
		}
	}