說明
之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？解法
可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的 排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。
那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數字不斷的分為兩個等分，直到最後剩一個數字為止，然後再反過來不斷的合併，就如下圖所示：
不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。
下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。
實作：C Java Python Scala Ruby
#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 [nb1[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 [nb1[0]] + sort(nb1, nb2[1..-1])
end
end