归并排序

 # 归并排序也属于一种分治算法

 1 local function _mergeArray(arr, first, mid, last, tempArr)
 2     local i = first
 3     local i_end = mid
 4 
 5     local j = mid + 1
 6     local j_end = last
 7 
 8     --print("mergeArray: [", first, ",", last, "]")
 9     --从小到大填充到临时数组
10     local count = 0
11     while i <= i_end and j <= j_end do
12         if arr[i] <= arr[j] then
13             count = count + 1
14             tempArr[count] = arr[i]
15             i = i + 1
16         else
17             count = count + 1
18             tempArr[count] = arr[j]
19             j = j + 1
20         end
21     end
22 
23     while i <= i_end do
24         count = count + 1
25         tempArr[count] = arr[i]
26         i = i + 1
27     end
28 
29     while j <= j_end do
30         count = count + 1
31         tempArr[count] = arr[j]
32         j = j + 1
33     end
34 
35     --放回原数组的所在区间, 相当于多元素swap
36     for i=1,count do
37         arr[first + i - 1] = tempArr[i]
38     end
39 end
40 
41 local function _mergeSort(arr, first, last, tempArr)
42     if first < last then
43         local mid = math.floor((first + last) / 2)
44         _mergeSort(arr, first, mid, tempArr)
45         _mergeSort(arr, mid+1, last, tempArr)
46         _mergeArray(arr, first, mid, last, tempArr)
47     end
48 end
49 
50 function MergeSort(arr)
51     local tempArr = {}
52     _mergeSort(arr, 1, #arr, tempArr)
53 end

测试代码：

1 function Test1()
2     local arr = { 19, 15, 37, 12, 25 }
3     MergeSort(arr)
4     print(table.concat(arr, ","))
5 end
6 Test1()

【参考】

排序算法：归并排序 - 知乎 (zhihu.com)