归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

2. 算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示

4. JavaScript 代码实现

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

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

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

5. Python 代码实现

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

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

6. Go 代码实现

func mergeSort(arr []int) []int {
	length := len(arr)
	if length < 2 {
		return arr
	}
	middle := length / 2
	left := arr[0:middle]
	right := arr[middle:]
	return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, 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
}

7. Java 代码实现

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

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

    protected 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;
    }

}

8. PHP 代码实现

function mergeSort($arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 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;
}

9. C++ 代码实现

void merge(vector<int>& arr, int l, int mid, int r) {
    int index = 0;
    int ptrL = l;
    int ptrR = mid;
    static vector<int>tempary;
    if (arr.size() > tempary.size()) {
        tempary.resize(arr.size());
    }
    while (ptrL != mid && ptrR != r) {
        if (arr[ptrL] < arr[ptrR]) {
            tempary[index++] = arr[ptrL++];
        } else {
            tempary[index++] = arr[ptrR++];
        }
    }
    while (ptrL != mid) {
        tempary[index++] = arr[ptrL++];
    }
    while (ptrR != r) {
        tempary[index++] = arr[ptrR++];
    }
    copy(tempary.begin(), tempary.begin() + index, arr.begin() + l);
}
void mergeSort(vector<int>& arr, int l, int r) { // sort the range [l, r) in arr
    if (r - l <= 1) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid, r);
    merge(arr, l, mid, r);
}

10. Rust 代码实现

/// 实现 1:
/// Safe Rust 实现，需要大量浅复制(move)，但不需要深拷贝，对primitive type排序较慢，但对没有 Copy Trait 的类型较快
fn merge_sort<T: Ord>(mut v: Vec<T>) -> Vec<T> {
    if v.len() < 2 {
        return v;
    }

    // Split the right half and sort them first
    let mut right = merge_sort(v.split_off(v.len() / 2));
    let mut left = merge_sort(v);

    let mut result = Vec::new();

    // 反向merge，因为 `Vec::remove(0)` 的复杂度是 `O(n)` 而且需要大量复制
    while !left.is_empty() && !right.is_empty() {
        if left.last().unwrap() > right.last().unwrap() {
            result.push(left.pop().unwrap());
        } else {
            result.push(right.pop().unwrap());
        }
    }
    result.extend(left.into_iter().rev());
    result.extend(right.into_iter().rev());
    result.reverse();

    result
}


/// 实现 2:
/// Safe Rust 实现，使用相对更少的复制，但需要更多的深拷贝。Primitive type排序速度更快，需要深拷贝的类型速度更慢
fn merge_sort2<T: Ord + Clone>(v: &mut [T]) {
    if v.len() < 2 {
        return;
    }

    let mid_idx = v.len() / 2;

    merge_sort2(&mut v[..mid_idx]);
    merge_sort2(&mut v[mid_idx..]);

    let mut temporary = Vec::with_capacity(v.len());

    let mut l = 0;
    let mut r = mid_idx;

    while l < mid_idx && r < v.len() {
        if v[l] < v[r] {
            temporary.push(v[l].clone());
            l += 1;
        } else {
            temporary.push(v[r].clone());
            r += 1;
        }
    }
    temporary.extend(v[l..mid_idx].iter().cloned());
    temporary.extend(v[r..].iter().cloned());

    for (item, dest) in temporary.into_iter().zip(v.iter_mut()) {
        *dest = item;
    }
}


/// 实现 3:
/// Unsafe Rust 实现，类似实现2，但使用 unsafe 避免了深拷贝，性能优于实现1与实现2
fn merge_sort3<T: Ord>(v: &mut [T]) {
    if v.len() < 2 {
        return;
    }

    // 可以在遇到较短的数组时使用插入排序，性能较佳。但即使不使用插入排序，此实现性能依然优于实现1与实现2
    if v.len() < 32 {
        insertion_sort(v);
        return;
    }

    let mid_idx = v.len() / 2;

    merge_sort3(&mut v[..mid_idx]);
    merge_sort3(&mut v[mid_idx..]);

    let alloc_array = |size: usize| -> *mut T {
        // 等同于C中: `(T*)malloc(sizeof(T) * size)`
        unsafe {
            std::alloc::alloc(
                std::alloc::Layout::array::<T>(size).unwrap_unchecked(),
            ) as *mut T
        }
    };
    let dealloc_array = |ptr: *mut T, size: usize| unsafe {
        // 等同于C中: `free(ptr)`
        std::alloc::dealloc(
            ptr as *mut u8,
            std::alloc::Layout::array::<T>(size).unwrap_unchecked(),
        )
    };

    let temporary = alloc_array(v.len());
    let mut used_len = 0;

    let mut l = 0;
    let mut r = mid_idx;

    unsafe {
        while l < mid_idx && r < v.len() {
            if v[l] < v[r] {
                temporary
                    .add(used_len)
                    .copy_from_nonoverlapping(v.as_ptr().add(l), 1);
                l += 1;
            } else {
                temporary
                    .add(used_len)
                    .copy_from_nonoverlapping(v.as_ptr().add(r), 1);
                r += 1;
            }
            used_len += 1;
        }

        let left_remain = mid_idx - l;
        temporary
            .add(used_len)
            .copy_from_nonoverlapping(v.as_ptr().add(l), left_remain);
        used_len += left_remain;

        let right_remain = v.len() - r;
        temporary
            .add(used_len)
            .copy_from_nonoverlapping(v.as_ptr().add(r), right_remain);

        v.as_mut_ptr().copy_from_nonoverlapping(temporary, v.len());
    }

    dealloc_array(temporary, v.len());
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

5.mergeSort.md

5.mergeSort.md

归并排序

2. 算法步骤

3. 动图演示

4. JavaScript 代码实现

5. Python 代码实现

6. Go 代码实现

7. Java 代码实现

8. PHP 代码实现

9. C++ 代码实现

10. Rust 代码实现

Files

5.mergeSort.md

Latest commit

History

5.mergeSort.md

File metadata and controls

归并排序

2. 算法步骤

3. 动图演示

4. JavaScript 代码实现

5. Python 代码实现

6. Go 代码实现

7. Java 代码实现

8. PHP 代码实现

9. C++ 代码实现

10. Rust 代码实现