爲什麼我們將數組劃分爲合併排序中的一個元素

假設我們有一個下面的列表

列表= 5 4 1 3 6 8 9 7

首先劃分列表分成4個-4元件。我們所說的左，右側列表

5 4 1 3 and 6 8 9 7

然後除以5 4 1 3成以下

5 4 and 1 3

然後分成5個和4成

5 4

排序時，我們將開始從排序最後一步，直到第1步（我們有4-4個元素）

問題：無論如何，當我們分列表直到1-1元素，我們在everymoment排序和合並列表，那麼爲什麼不把列表除以4-4元素。因爲在這種情況下，我們也會合並列表。爲什麼迭代到1-1元素

來源

2016-05-31 Nitesh

噹噹前迭代有一個或兩個元素時，會發生_base case_。發生這種情況時，算法將返回一個元素，或者排序兩個元素。這假設你正在使用mergesort的遞歸實現，我認爲你是。 –

由於只有一個元素的數組已經排序。 – Shravan40

爲了闡明Tim Biegeleisen的評論，合併排序的自底向上/迭代實現跳過了數組的所有遞歸分割，並且首先假定一個大小爲N的數組是N個大小爲1的子數組。合併排序的大多數現實世界實現是自底向上合併排序的一些變體，如[timsort]（http://en.wikipedia.org/wiki/Timsort）。 – rcgldr

1元素列表自然排序。我們合併兩個1元素的排序列表以獲得2元素排序列表，然後合併2元素排序列表以獲得4元素排序列表等等。

合併過程旨在對排序的名單，所以我們不能申請合併無序5 4 1 3和6 8 9 7名單

來源

2016-05-31 10:53:36 MBo

好吧。謝謝 – Nitesh

因爲如果你這樣做了合併排序方式存在，說一個不變一個合併的列表（在分割之後）被排序，這意味着在合併分割的列表之後的每個級別，合併的列表被排序。

例如，如果您在拆分爲4-4後立即合併，則會比較兩個列表中的第一項，而這兩個值可能不是這些拆分列表中的最小值，這意味着您最終會得到結果列表中排序最有可能不排序。

來源

2016-05-31 10:55:12 Glubus

理論上，這是因爲合併過程需要採取兩個排序列表。 4元素列表未排序，而1元素列表爲。

實際上，我們不會將列表拆分爲單個元素。因爲合併排序不是小列表最有效的排序算法，插入排序是。所以常見的優化是使用插入排序來對小列表進行排序，並將它們與合併排序合併。

來源

2016-05-31 11:06:43

爲什麼我們將數組劃分爲合併排序中的一個元素

回答

相關問題