[問題] Wiki 的合併排序法

[obelisk0114 (追風箏的孩子)]

這個連結是中文維基百科的合併排序法

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

在 java 的疊代版程式如下

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;

    // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
    for(block = 1; block < len*2; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
                result[low++] = arr[start1] < arr[start2] ? arr[start1++] :
arr[start2++];
            }
            while(start1 < end1) {
                result[low++] = arr[start1++];
            }
            while(start2 < end2) {
                result[low++] = arr[start2++];
            }
        }
        int[] temp = arr;
        arr = result;
        result = temp;
    }
    result = arr;
}


------------------

這個程式看起來應該是使用 bottom-up 來實作

但是他有幾個地方我有點疑問

1. for(block = 1; block < len*2; block *= 2)

我覺得 block < len 好像就可以了 ?

2. int mid = (start + block) < len ? (start + block) : len;

mid 只有在只剩單一元素時才會 >= len,但是只剩單一元素也不需做比較

所以好像不需要判斷 ?

3.

int[] temp = arr;
arr = result;
result = temp;

一開始我想就是把結果存回去,用

for (int i = 0; i < arr.length; i++) {
    arr[i] = result[i];
}

但是他卻用淺層複製做交換

為何要用淺層複製來做交換 ? 速度會比較快嗎 ?

--
    肝不好           ▁▁        ●       ◤            肝若好
        人生是黑白的     ▏             ◤                   考卷是空白的
                         ▏           ◤                  、 ﹐
  ●      ●b     囧     ▎  ●> ● ◤  ▌ ﹍﹍ ０      ▊囧＞ 幹...
  ▲      ■┘    ■     ▎  ■ █◤    ▌      ㄏ▋     ︶■
 〈﹀     ∥  ▁▁∥     ▎ ﹀〉◤      ▋        ▊      〈\  ψcockroach727

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.95.52.50
※ 文章網址: https://www.ptt.cc/bbs/java/M.1481845143.A.7D3.html
→ ssccg: 3當然比較快啊，每次loop少copy整個array一次
為何要加入交換的步驟, 讓 result 和 arr 不是指向相同的參考嗎 ?
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 09:33:45
→ ssccg: loop裡都是從來源arr到目標result，做完一次當然要把來源改
→ ssccg: 成指向這輪的結果(arr=result)，至於result=temp(arr)只是
→ ssccg: 重新利用現有空間而已
我把交換指向註解掉,結果會錯誤

假如只是為了利用現有空間,應該沒有問題

→ ssccg: 另外這不是淺層複製，根本沒有複製，是交換指向的array物件
→ ssccg: 1沒錯到block < len就可
→ ssccg: 2 當然還是要判斷只是不用多做只剩一個block直接break就好
這樣 start + break 就會等於 len

應該是不會有大於 len 的情形吧
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 10:43:14
→ ssccg: 當然會錯誤啊，不利用現有空間不是不用做事
→ ssccg: 是要像一開始那樣result = new int[len];
→ ssccg: 然後你的等於大於len我看不懂你是要說什麼...
→ ssccg: 我是說start + block < len這判斷一定要做，當這條件不成立
→ ssccg: (start + block >= len)時，代表這輪的兩個block中後面那個
→ ssccg: 沒有了，只有一個block，至於是>還是=是差在前面那個block
→ ssccg: 大小是不是剛好等於這輪的block，跟要不要這判斷沒關係
int mid = (start + block) < len ? (start + block) : len;

是不是只需要寫成這樣就好 ?

int mid = start + block

會出現 mid 大於 len 的情形嗎 ?
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 11:06:21
→ ssccg: 舉例來說block = 2, start = 4, len = 5
→ ssccg: 至少要加 if (mid >= len) break;
→ obelisk0114: 了解了, Thanks