Merging

归并排序

• 时间复杂度 O(n)
• 空间复杂度 O(log2n)

PHP：

function merge(array $left, array $rigth) : array 
{
    $result = array();

    while (count($left) && count($rigth)) {
        $result[] = $left[0] < $rigth[0] ? array_shift($left) : array_shift($rigth);
    }

    return array_merge($result, $left, $rigth);
}

function al_merge_sort(array $arr) : array 
{
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }

    $mid = intval($len / 2);

    $left = array_slice($arr, 0, $mid);
    $rigth = array_slice($arr, $mid);

    $left = al_merge_sort($left);
    $rigth = al_merge_sort($rigth);

    return merge($left, $rigth);
}

print_r(al_merge_sort([9, 3, 5, 6, 7, 1, 2, 55, 56]));

// Array
//     (
//         [0] => 1
//         [1] => 2
//         [2] => 3
//         [3] => 5
//         [4] => 6
//         [5] => 7
//         [6] => 9
//         [7] => 55
//         [8] => 56
//     )

Go：

package main

import (
    "fmt"
)

func merge(left, rigth []int) (result []int) {

	l, r := 0, 0
	
    for l < len(left) && r < len(rigth) {
        if left[l] < rigth[r] {
            result = append(result, left[l])
            l ++
        } else {
            result = append(result, rigth[r])
            r ++
        }
    }

    result = append(result, left[l:]...)
    result = append(result, rigth[r:]...)

    return 
}

func al_merg_sort(arr []int) []int {
    length := len(arr)

	if length <= 1 {
		return arr
    }
    
    mid := length / 2

    left := al_merg_sort(arr[:mid])
    rigth := al_merg_sort(arr[mid:])

    return merge(left, rigth)
}

func main() {
    arr := []int{31, 4, 5, 27, 18, 1 ,3, 6, 8}
    fmt.Println(al_merg_sort(arr))
}