算法思想

归并排序分为三个步骤：

1.分解：将数列分解成n个子数列。(如果是将数列分成2个子数列则为2路归并)

2.治理：对每个子数列进行排序操作

3.合并：将两个排好序的子数列进行合并生成新的数列

算法实现

• PHP实现

<?php

function mergeSort($arr)
{
	if (count($arr) < 2) {
		return $arr;
	}
	$middle = floor(count($arr) / 2);
	$left = array_slice($arr, 0, $middle);
	$right = array_slice($arr, $middle);

	return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
	$result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left))
        $result[] = array_shift($left);

    while (count($right))
        $result[] = array_shift($right);

    return $result;
}
$arr = [13,1, 7,11, 5, 3, 9, 8];
$res = mergeSort($arr);
print_r($res);

• Java实现

public static void main(String[] args)
    {
        int [] arr = {13,1, 7,11, 5, 3, 9};

        int[] result = mergeSort(arr);
        System.out.println(Arrays.toString(result));
    }
    public static int[] mergeSort(int[] array)
    {
        if (array.length < 2) {
            return array;
        }
        int middle = (int) Math.floor(array.length / 2);
        int[] left = Arrays.copyOfRange(array, 0, middle);
        int[] right = Arrays.copyOfRange(array, middle, array.length);

        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right)
    {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length >0) {
            if (left[0] <= right[0]) {
                result[i ++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i ++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        while (left.length >0) {
            result[i ++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i ++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }

• Python实现

def mergeSort(array):
    if len(array) < 2:
        return array

    middle = math.floor(len(array) / 2)
    left, right = array[0:middle], array[middle:]
    return merge(mergeSort(left), mergeSort(right))


def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    while len(left) > 0:
        result.append(left.pop(0))
    while len(right) > 0:
        result.append(right.pop(0))
    return result


if __name__ == '__main__':
    # app.run(debug=True)
    arr = [13, 1, 7, 11, 5, 3, 9]
    res = mergeSort(arr)
    for i in range(len(res)):
        print("%d" % res[i])

• GO实现

func main() {
	arr := []int{13, 1, 7, 11, 5, 3, 9}
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

func mergeSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	middle := len(arr) / 2
	left := arr[0:middle]
	right := arr[middle:]
	return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) []int {
	var result []int
	for len(left) > 0 && len(right) > 0 {
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	for len(left) > 0 {
		result = append(result, left[0])
		left = left[1:]
	}
	for len(right) > 0 {
		result = append(result, right[0])
		right = right[1:]
	}
	return result
}