[新手][問題] recursive---merge sort

[flax00298 (NI)]

它的概念是說

我把一個大的矩陣弄成對半的兩個小矩陣去排

排完再把他們黏起來

然後那兩個對半的SORT也是在拆成兩個更小的這樣

可是我覺得非常的奇怪

因他的作法不就是說像這樣這樣嗎?這樣根本沒有辦法SORT阿


        2 65 98 999 564 3 -3 57

                變成

        2 65 98 999    564 3 -3 57

                然後再變成

        2 65    98 999    564 3    -3 57

                最後是
        2    65    98    999    564    3    -3    57


這時候八個小矩陣很理所當然的

因為都只有一個ELEMENT

就是SORTED的了

接下來把它黏起來不是就變成

        2 65 98 999 564 3 -3 57

阿不是根本就沒有排嗎?

而且依照他的概念好了

拆成兩個小的去SORT

變成

        2 65 98 999      -3 3 57 564


阿然後黏起來

        2 65 98 999 -3 3 57 564

這樣不是根本沒有排好嗎?

請各位大大們替我解答一下

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.233.146.73
※ 編輯: flax00298       來自: 125.233.146.73       (07/03 17:53)
推 littleshan:「merge」並不是單純把兩個陣列「黏起來」
→ littleshan:而是在 linear time 內把它們合併成一個已排序的陣列
→ flax00298:對不起...I DONT GET IT...
→ flax00298:可以麻煩清楚一點嗎?還是這已經是最清楚了ˊˋ
→ kchiu:Merge的概念是把兩個sorted array合併成一個sorted array
→ flax00298:是沒錯~可是我不懂黏起來再牌還不是要排?
→ flax00298:這樣根直接排不就又變成一樣了...
→ kchiu:把兩個排好的合併成一個排好的 可以在linear time辦到
推 Ebergies:不一樣, 比較的次數不一樣
→ flax00298:喔喔喔!!!我懂了~謝謝你們大家QQ