合併排序

今日有兩筆已排序的資料，如何將它們合併並排序？

解法思路

合併排序基本上是用來將兩筆已排序的資料合併與排序，如果讀入的資料尚未排序，要先利用其他排序方式來處理這兩筆資料，然後再將排序好的資料合併。

如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序可以儘量利用資料已排序的部份，來加快排序效率，小筆資料的排序較為快速，如果小筆資料排序完成後，合併處理時，因為兩筆資料都有排序了，合併排序時會比單純讀入全部資料排序來的有效率。

可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其他排序方式？基本上是可行，可將全部數字不斷地分為兩個等分，直到最後剩一個數字為止，然後再反過來不斷地合併，只是效率不彰，因為分割會花去額外的時間：

合併排序

程式實作

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX1 10 
#define MAX2 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

int partition(int[], int, int); 
void quickSort(int[], int, int); 
void mergeSort(int[], int, int[], int, int[]); 

int main(void) { 
    srand(time(NULL)); 
    
    int number1[MAX1] = {0}; 
    int number2[MAX1] = {0}; 
    int number3[MAX1+MAX2] = {0}; 

    printf("排序前："); 
    printf("\nnumber1[]："); 
    int i;
    for(i = 0; i < MAX1; i++) { 
        number1[i] = rand() % 100; 
        printf("%d ", number1[i]); 
    }
    printf("\nnumber2[]："); 
    for(i = 0; i < MAX2; i++) { 
        number2[i] = rand() % 100; 
        printf("%d ", number2[i]); 
    } 

    // 先排序兩筆資料 
    quickSort(number1, 0, MAX1-1); 
    quickSort(number2, 0, MAX2-1); 

    printf("\n排序後："); 
    printf("\nnumber1[]："); 
    for(i = 0; i < MAX1; i++) 
        printf("%d ", number1[i]); 
    printf("\nnumber2[]："); 
    for(i = 0; i < MAX2; i++) 
        printf("%d ", number2[i]); 

    // 合併排序 
    mergeSort(number1, MAX1, number2, MAX2, number3); 

    printf("\n合併後："); 
    for(i = 0; i < MAX1+MAX2; i++) 
        printf("%d ", number3[i]); 
    
    printf("\n"); 

    return 0; 
} 

int partition(int number[], int left, int right) { 
    int s = number[right]; 
    int i = left - 1; 
    int j;
    for(j = left; j < right; j++) { 
        if(number[j] <= s) { 
            i++; 
            SWAP(number[i], number[j]); 
        } 
    } 
    SWAP(number[i+1], number[right]); 
    return i+1; 
} 

void quickSort(int number[], int left, int right) { 
    if(left < right) { 
        int q = partition(number, left, right); 
        quickSort(number, left, q-1); 
        quickSort(number, q+1, right); 
    } 
} 

void mergeSort(int number1[], int M, int number2[], 
                int N, int number3[]) { 
    int i = 0, j = 0, k = 0; 
    while(i < M && j < N) { 
        if(number1[i] <= number2[j]) 
            number3[k++] = number1[i++]; 
        else 
            number3[k++] = number2[j++]; 
    } 

    while(i < M) 
        number3[k++] = number1[i++]; 
    while(j < N) 
        number3[k++] = number2[j++]; 
}

public class Sort {
    // number1、number2 必須排序過
    public static int[] merge(int[] number1, int[] number2) {
        int[] number3 = new int[number1.length + number2.length];
        
        int i = 0, j = 0, k = 0; 
        while(i < number1.length && j < number2.length) { 
            if(number1[i] <= number2[j]) 
                number3[k++] = number1[i++]; 
            else 
                number3[k++] = number2[j++]; 
        } 

        while(i < number1.length) 
            number3[k++] = number1[i++]; 
        while(j < number2.length) 
            number3[k++] = number2[j++];
        
        return number3;
    }
}

def sort(nb1, nb2):
    if len(nb1) == 0: return nb2
    elif len(nb2) == 0: return nb1
    elif nb1[0] < nb2[0]: return [nb1[0]] + sort(nb1[1:], nb2)
    else: return [nb2[0]] + sort(nb1, nb2[1:])
    
number1 = [4,13,6,6,2,7,2,9,29]
number2 = [4,13,6,6,2,7,2,9,29]
number1.sort()
number2.sort()
print(sort(number1, number2))

object Sort {
    def merge(nb1: List[Int], nb2: List[Int]): List[Int] = 
        (nb1, nb2) match {
            case (Nil, _) => nb2
            case (_, Nil) => nb1
            case (head1 :: tail1, head2 :: tail2) =>
                if(head1 <= head2) head1 :: merge(tail1, nb2)
                else head2 :: merge(nb1, tail2)
        }
}

Sort.merge(List(1,2,3,4,5,6,7), List(1,2,3,4,5,6,7)).foreach(print)

def sort(nb1, nb2)
    if nb1.empty? 
        return nb2
    elsif nb2.empty? 
        return nb1
    elsif nb1[0] < nb2[0] 
        return [nb1[0]] + sort(nb1[1..-1], nb2)
    else 
        return [nb2[0]] + sort(nb1, nb2[1..-1])
    end
end

function sort(nb1, nb2) {
    if(nb1.length == 0) {
        return nb2;
    }
    else if(nb2.length == 0) {
        return nb1;
    }
    else if(nb1[0] < nb2[0]) {
        return [nb1[0]].concat(sort(nb1.slice(1), nb2));
    }
    else {
        return [nb2[0]].concat(sort(nb1, nb2.slice(1)));
    }
}

let number1 = [4,13,6,6,2,7,2,9,29];
let number2 = [4,13,6,6,2,7,2,9,29];
number1.sort((a, b) => a - b);
number2.sort((a, b) => a - b);
console.log(sort(number1, number2));

quickSort [] _ = []
quickSort (x:xs) compare = 
    let before = filter (not . (compare x)) xs
        after = filter (compare x) xs
    in (quickSort before compare) ++ [x] ++ (quickSort after compare)


mergeSort xs1 [] _ = xs1
mergeSort [] xs2 _ = xs2
mergeSort (x1:xs1) xs2 compare = 
    let before = filter (not . (compare x1)) xs2
        after = filter (compare x1) xs2
    in before ++ [x1] ++ (mergeSort xs1 after compare)

main =
    let xs1 = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]
        xs2 = [13, 8, 10, 21, 5, 7, 1, 3, 2, 9]
        sorted1 = quickSort xs1 (>)
        sorted2 = quickSort xs1 (>)
        sortedAll = mergeSort sorted1 sorted2 (>)
    in print sortedAll