|
- Welcome to Mergesort Interactive Tutorial.
Input your own values:
- Explore the content of the diagram: move mouse over / tap on the text.
- (1) Mergesort concepts.
- At the top of the diagram, an initial list contains random values (not
sorted).
- At the bottom of the diagram, a sorted list is the result of the algorithm.
- Mergesort uses the concept of merging of two lists, at each step.
- For example, at the first level, two lists with a single value (each
one) are merged into a sorted list.
- In a second example, at the next level, two lists with sorted values
are merged into another sorted list.
- This procedure is repeated until the last level, with a resulting sorted
list containing all values (as described in the next steps).
- (2) Mergesort scan process.
- A sub-task of Mergesort is the scan process. The scan process requires two sorted inputs to produce a
sorted output.
- Since the inputs are sorted, the scan can be done only once for each input. While scanning the
inputs, Mergesort then produces the sorted output.
- For example, at the last level, Mergesort scans two inputs that produce
the output.
- At the beginning of the scan (of each input), the smallest value (for the output)
is produced.
- The scan process always chooses the smaller value (between the two inputs) to produce the next output
value.
- At the end of the scan (of both inputs), the largest value (for the output) is
produced.
- (3) Advanced concepts.
- Mergesort is an efficient sort algorithm, and also a stable sort algorithm.
- Mergesort is usually employed as an external memory algorithm (over large sets of already sorted
values).
- External memory means: the algorithm does not require main memory (RAM), instead it uses a slower memory
(for example, disk drives or tape drives).
- In 1945, John von Neumann developed the
Mergesort algorithm for EDVAC (a vacuum tube computer).
- The end.
Also, visit Quicksort Interactive Tutorial.
|
|
