Content deleted Content added
Reorganized discussion; reformatted text. |
|||
Line 1:
== Nomenclature issue ==
I would like to know if it is standard nomenclature to call "merge algorithms" the ones that follow.
Line 24 ⟶ 26:
[[User:Pablo.cl|Pablo.cl]] 01:50, 26 May 2004 (UTC)
== Nomenclature response ==
== Minor change to python example ==▼
The example originally had a[0] < b[0] rather then a[0] <= b[0]▼
as the basis for using the item from the a[] array. This would▼
not result in a stable sort, since equal elements would have been▼
selected from the b[] array before those from the a[] array.▼
The change ensures stability.▼
It's a bit of a shame that one sees so many assertions that▼
merge sort is stable. As the uncorrected example shows,▼
it's easily possible to write an unstable, but otherwise▼
valid, merge sort. -- jpl▼
----
Line 45 ⟶ 36:
Updating files: the updates, i.e. the changed records, are "batched" together, i.e. saved, and sorted into key order. Then the master file is read, one record at a time, until a record with the same key as the first transaction is found. This master file record is then updated and then the process is repeated.
The updating is done as follows:
* For magnetic tape. Put the updates in a separate file and merge the master and the update to give a new master.
* For a disk, the easiest method is to associate a pointer with each record leading to the next one (linked list). Individual records can be scrubbed and replaced by reseting pointers.
In general, if only one master file is available, it is not altered, but a new master is produced by merging.
Line 60 ⟶ 48:
In any case, each of these things I called "merge algorithms" when I wrote this page can be conceptualized as the composition of some other function over sequences and the ordinary sorting merge, the one that produces a multiset union.
The kragen-hacks reference carries no weight in this case, because kragen-hacks is written by the same person who promulgated this questionable nomenclature in this Wikipedia article in the first place: me. If we decide to accept the term "merge" for this larger class of algorithms beyond just multiset union, it would have to be on the basis of documented terminology usage by people besides me. In my eyes, the fact that Knuth uses the term with a clearly more restricted meaning in mind creates a substantial burden of proof.
-- KragenSitaker
▲== Minor change to python example ==
▲The example originally had a[0] < b[0] rather then a[0] <= b[0]
▲as the basis for using the item from the a[] array. This would
▲not result in a stable sort, since equal elements would have been
▲selected from the b[] array before those from the a[] array.
▲The change ensures stability.
▲It's a bit of a shame that one sees so many assertions that
▲merge sort is stable. As the uncorrected example shows,
▲it's easily possible to write an unstable, but otherwise
▲valid, merge sort. -- jpl
| |||