Merge algorithm

wikipedia Merge algorithm

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.

Application

The merge algorithm plays a critical role in the merge sort algorithm, a comparison-based sorting algorithm. Conceptually, merge sort algorithm consists of two steps:

1、Recursively divide the list into sublists of (roughly) equal length, until each sublist contains only one element, or in the case of iterative (bottom up) merge sort, consider a list of n elements as n sub-lists of size 1. A list containing a single element is, by definition, sorted.

NOTE:

1、需要考虑 "iterative (bottom up) merge sort" 如何实现

2、Repeatedly merge sublists to create a new sorted sublist until the single list contains all elements. The single list is the sorted list.

NOTE:

1、这其实就非常类似于 k-way merge

The merge algorithm is used repeatedly in the merge sort algorithm.

An example merge sort is given in the illustration. It starts with an unsorted array of 7 integers. The array is divided into 7 partitions; each partition contains 1 element and is sorted. The sorted partitions are then merged to produce larger, sorted, partitions, until 1 partition, the sorted array, is left.

Merging two lists

NOTE:

1、合并两个是相对简单的

Merging two sorted lists into one can be done in linear time and linear space. The following pseudocode demonstrates an algorithm that merges input lists (either linked lists or arrays) A and B into a new list C.[1][2]:104 The function head yields the first element of a list; "dropping" an element means removing it from its list, typically by incrementing a pointer or index.

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B

    return C

NOTE:

1、leetcode 21. 合并两个有序链表

When the inputs are linked lists, this algorithm can be implemented to use only a constant amount of working space; the pointers in the lists' nodes can be reused for bookkeeping and for constructing the final merged list.

In the merge sort algorithm, this subroutine is typically used to merge two sub-arrays A[lo..mid], A[mid..hi] of a single array A. This can be done by copying the sub-arrays into a temporary array, then applying the merge algorithm above.[1] The allocation of a temporary array can be avoided, but at the expense of speed and programming ease. Various in-place merge algorithms have been devised,[3] sometimes sacrificing the linear-time bound to produce an O(n log n) algorithm;[4] see Merge sort § Variants for discussion.

K-way merging

Main article: K-way merge algorithm

NOTE: 参见 K-way-merge-algorithm 章节。

LeetCode 试题

下面总结一些归并的试题。

https://leetcode-cn.com/problemset/all/?search=%E5%90%88%E5%B9%B6%20

Merge sequence

一、 merge two sequence

leetcode 912. 排序数组 (merge sort) 和 leetcode 21. 合并两个有序链表

merge sortmerge的部分，和 leetcode 21. 合并两个有序链表的逻辑是非常类似的。

下面的是合并两个序列的题目:

1、leetcode 88. 合并两个有序数组

2、

二、merge multiple sequence

leetcode 23. 合并K个升序链表

两两合并

leetcode 23. 合并K个升序链表中，给出了递归写法和迭代写法；

三、合并有序序列

合并有序数组

合并有序链表

1、我写了套框架，把滑动窗口算法变成了默写题中:

**快慢指针**最神奇，链表操作无压力。

归并排序找中点，链表成环搞判定。