Talk:Merge algorithm: Difference between revisions

Revision as of 13:23, 23 June 2019

Latest revision as of 03:28, 6 February 2024

(14 intermediate revisions by 8 users not shown)

Line 1:

{{WikiProject Computerbanner scienceshell|Classclass=Start|Importance=Low}}

{{WikiProject Computer science|importance=Low}}

}}

== Nomenclature issue ==

Line 127 ⟶ 128:

== Merge K-way merge algorithm article into this one ==

The article [[K-way merge algorithm]] largely duplicates content in the K-way merging section in this article, so I think it should be merged (this is not just a pun, I promise). I also suspect that the topic is not notable enough to merit its own article. &mdash;&nbsp;'''[[User:Pzoxicuvybtnrm|<fontspan colorstyle="color:#750404;">P</fontspan>]][[User talk:Pzoxicuvybtnrm|<fontspan colorstyle="color:#254117;">C</fontspan>]][[Special:Contributions/Pzoxicuvybtnrm|<fontspan colorstyle="color:#062159;">B</fontspan>]]''' 21:59, 9 December 2017 (UTC)

:I agree, the two articles have far too much overlap to be separate. Possibly if this article were expanded in a different direction the topics could be separately notable, but with the current content they are not. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:13, 9 December 2017 (UTC)

*'''Oppose''' The article is written in appropriate [[WP:SUMMARYSTYLE]], the K-way merging section summarize this article while this article gives significantly more details [[User:Trialpears|Trialpears]] ([[User talk:Trialpears|talk]]) 11:25, 15 May 2019 (UTC)

::Closing, given the uncontested policy-based argument. [[User:Klbrain|Klbrain]] ([[User talk:Klbrain|talk]]) 13:23, 23 June 2019 (UTC)

== Language support - C++ - std::inplace_merge ==

The term in place may be mis-leading here. std::inplace_merge may use auxiliary storage to implement the merge. It can throw an exception if it can't allocate enough memory.<ref>https://en.cppreference.com/w/cpp/algorithm/inplace_merge</ref>. Microsoft / Visual Studio attempts to allocate memory, but can perform the merge even if memory allocation fails.<ref>https://docs.microsoft.com/en-us/previous-versions/awc3s8k6(v=vs.140)</ref>.

{{reflist_talk}}

== Possible typo ==

should not it be a s+1 there? (the lower line beneath):

in parallel do

merge(A[i...r], B[k...s], C[p...t])

merge(A[r+1...j], B[s...ℓ], C[t+1...q])

<!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/37.47.172.117|37.47.172.117]] ([[User talk:37.47.172.117#top|talk]]) </small>

== Difference between the merge algorithm and merge sort? ==

What is the difference between the merge algorithm and [[merge sort]]? The article says that the merge algorithm plays a critical role in the merge sort algorithm, but according to how the article describes the merge algorithm, it seems to me that it ''is the same thing'' as merge sort. So, what is the difference between the two algorithms, if there is a difference? I think this should be clarified early on in the article. —[[User:Kri|Kri]] ([[User talk:Kri|talk]]) 17:52, 23 August 2023 (UTC)

: {{re|Kri}} The merge algorithm takes two sorted chains (lists, sequences, arrays, ...) of data and creates a new chain (sometimes by copying the items of source data, sometimes by interleaving them, depending on the data structure in use), containing all items of both source chains in the proper order. Merge sort takes unsorted chain of data, decomposes it into multiple chains and successively merges them to construct a finał sorted chain of all source data. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 20:14, 23 August 2023 (UTC)

::Yes. The merge algorithm is a subroutine in merge sort, not the whole merge sort. It is also used as a subroutine in some other algorithms unrelated to sorting. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 01:14, 24 August 2023 (UTC)

:::{{re|David Eppstein}} Thank you for clarification. {{smiley}} [[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 10:33, 29 August 2023 (UTC)

::::Thank you for the answers; that makes sense! I have updated the text under the image in the article to reflect that. —[[User:Kri|Kri]] ([[User talk:Kri|talk]]) 19:42, 29 August 2023 (UTC)

: {{re|Kri}} What David said about a ''𝄪subroutine𝄪'' above applies to words ''𝄪successively merges them𝄪'' in my answer. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 10:33, 29 August 2023 (UTC)