ROSALIND｜Merge Sort (MS)

發表於 更新於

以 merge sort 遞增排序一個整數數列。

Given: A positive integer $n \leq 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: A sorted array $A[1..n]$.

(https://rosalind.info/problems/ms/)

在 Merge Two Sorted Arrays (MER) 之中，我們學會如何合併兩個有序數列。將此功能結合遞迴，應用在被拆成小片段的數列上，就能實現 merge sort。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def mer(S, T):
    merged = []
    s, t = 0, 0
    while s < len(S) and t < len(T):
        if S[s] <= T[t]:
            merged.append(S[s])
            s = s + 1
        else:
            merged.append(T[t])
            t = t + 1
    merged.extend(S[s:])
    merged.extend(T[t:])
    return merged
def ms(l):
    if len(l) <= 1:
        return l
    mid = len(l) // 2
    left = ms(l[:mid])
    right = ms(l[mid:])
    return mer(left, right)

題外話，這題我竟然不靠 AI 和 Google 一次就寫對。Rosalind 將算法題拆成關聯的小題目，循序漸進地引導練習的策略對我蠻友善的：題目不會難到第一眼看不出解法，而且每次都會用到先前的概念，可以達到復習的效果。