MergeSort - Algoviz Wiki

Works

Yes

Description

Bar-swapping in a stepwise or continuous fashion with explanations of the code taking place. Instrumented for AlgorithmSimulation (compares and copies). Also has a separate simulation mode which dispenses with the swapping bars.

Evaluation

One of the best swapping-bars visualizations, since it includes a stepwise component. Main drawback is no ability to add your own datasets, and the built-in dataset is randomized each time.

Teaching the Concept; Comparison

Screenshots

Videos

References

First Visited

2006-09-06

Last Visited

2010-02-11

Last Updated

2004-06-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/sorts/MergeSort.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Merge Sort

Recommendation

Recommended

Link

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Myles McNally

Institution

Alma College

Project

JHAVÉ

Works

Yes

Description

Visualization for Merge Sort. Includes dynamically highlighted pseudo code. Users can select random data, or give their own data. As the presentation progresses, the sub-array processing is shown as branches of a virtual tree.

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. This is an exceptionally clear presentation of Merge Sort. The presentation mechanism for showing the subarray processing is effective. The AV is supported by an HTML page that shows complete pseudocode and gives some guidance on using the AV, though the guide questions are not so extensive as for some other JHAVÉ topics.

Step Control; Questions; Random Data; User Data

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

Clicking on the link above will take you to a login page for Jhave. If you do not want to create an account at jhave.org, use anonymous@anonymous.com as your user name and anonymous as your password when you are asked to login. You will then be taken to the Jhave page for this AV. Some Jhave AVs include a tutorial on how the AV itself or the underlying algorithm works. At the bottom are links to the AV (you can run it with a built-in quiz system on or off). The first time you try to run any Jhave exercise, you will have to download the Jhave webstart application. This should happen automatically when you click the link. (You might need to install Java WebStart if it is not on your machine.) Once you download the Jhave application, the AV should start automatically. You can then step through the AV by repeatedly clicking the right arrow button. Occasionally, you will be given a multiple-choice or short-answer question to answer.

First Visited

2008-07-08

Last Visited

2008-07-08

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hope.edu/~dershem/ccaa/animator/Animator.html

Edit

You may edit this entry if you have an account.

The Animator - Mergesort

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Peter Brummund

Institution

Hope College

Project

Animator

Works

Yes

Description

Traditional swapping-bars animation with user-selectable colors, number of blocks, a few data set choices, speed control, and AlgorithmSimulation-type readouts for number of swaps and number of compares. Also has bounce-along Java code.

Evaluation

This is an OK visualization if all you need is an animation. May not do an adequate job explaining how the algorithms work. Strength: This implementation has a very helpful and somewhat unusual feature: It shows what subset of the array is currently being worked on by means of hierarchical bars at the top. Weakness: The merge implementation is horrible. It attempts to avoid using an auxiliary array. Instead, it uses an inner loop that gives this algorithm an O(n^2) worse case performance. Has some screen update bugs. Garish colors.

Animation; Random Data

Lecture Aid; Teaching the Concept

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2009-05-04

Last Updated

1997

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.brian-borowski.com/Sorting/

Edit

You may edit this entry if you have an account.

Sorting Demo - Mergesort

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Brian S. Borowski

Institution

Seton Hall University

Project

Borowski's Collection

Works

Yes

Description

Includes bounce-along pseudocode, user-defined and built-in datasets, speed control, and AlgorithmSimulation instrumentation (comparisons, exchanges). No stepwise operation.

Evaluation

Cluttered UI and lack of stepwise operation keep this out of the "recommended" list, but it's not a bad start.

Teaching the Concept; Debugging

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-05

Last Updated

2000

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://dbs.mathematik.uni-marburg.de/research/projects/dsn/

Edit

You may edit this entry if you have an account.

Data Structures Navigator - Mergesort

Recommendation

Recommended

Link

Delivery Method

Java Application

License

Unavailable

Language

English

Author

Jens-Peter Dittrich; Jochen van den Bercken; Tobias Schäfer; Marcus Klein

Institution

Phillips-University of Marburg

Project

Data Structure Navigator

Works

Yes

Description

Shows the steps for mergesort by building up a tree-like structure for splitting the array into subarrays and merging them back together. Stepwise/continuous operation with speed control, swaps blocks containing letters. Gives options about which steps to visualize. Shows history of operations. Multiple built-in data sets. Shows recursive descent nicely.

Evaluation

This would be better if it had some pseudocode or explanation for what was happening. The tree structure model needs a bit of interpretation for students to understand, since in reality there is no such tree. Just a little explanation would make this clear.

Step Control; Animation; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-16

Last Updated

2001-03-19

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Comparison Sorts - Merge Sort

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

Part of DSV integrated visualization suite. Swapping-bars paradigm with speed control and stepwise operation. Only random data sets. This mergesort visualization uses a bar-swapping paradigm with an auxiliary array to show the merging operations. The user can step through the visualization or run it as an animation, with a slider used to control the speed. The visualization shows actual values for the bars and array indices.

Evaluation

The visualization is not enough as a standalone explanation for the mergesort algorithm. There is no code associated with the visualization. The auxiliary array idea is not sufficient to explain how merging works. The user might miss having a history of actions. There might be some confusion as to how to reset and restart the presentation. This tool could possibly be used as a teaching aid to visualize an explanation, but it’s not recommended as an independent learning tool. Also it really needs to be accompanied by some explanation.

Animation; Step Control; Random Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-01

Last Updated

2006-04-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://nova.umuc.edu/~jarc/idsv

Edit

You may edit this entry if you have an account.

Interactive Data Structure Visualization - Efficent Sorts (Merge Sort)

Recommendation

Recommended

Link

Delivery Method

Java Applet

License

By Request

Language

English

Author

Duane J. Jarc

Institution

University of Maryland University College

Project

IDSV

Works

Yes

Description

Bar-swapping with speed control animation or step-through control. Also has an "I'll Try" mode where viewers are asked to select what bars will be swapped.

Evaluation

The bar-swapping presentation is nicely done, showing what subarrays are merged to make runs. What makes this AV stand out is the "I'll Try" mode. Here, the user must demonstrate understanding about how the algorithm works by choosing the values to swap. The only flaw is that there is no pseudocode or other explanation of the algorithm, so the user has to come to this exercise with some other source of information about the algorithm.

Random Data; Step Control; Animation; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2007-04-05

Last Visited

2008-07-15

Last Updated

2005-12-03

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=39

Edit

You may edit this entry if you have an account.

Animal - Merge Sort

Recommendation

Has Potential

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

Marc-Daniel Haunschild

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

Presents a slideshow walking through an example of mergesort.

Evaluation

Generally clear visualization, with one important caveat. This does not implement the standard "simple" mergesort, but rather an optimized variant where the right subarray is copied in reverse order, to simplify the stopping criteria. This can be good or bad... it is bad if a student comes to this without proper support about what is going on, since the AV itself does not discuss the issue (there is no supporting description or pseudocode with the AV). It is good for an instructor who wants to be able to demonstrate the optimized version as part of their lecture. Another problem is that only half the array is actually sorted in the example, which could be confusing.

Animation; Step Control; Canned Data

Lecture Aid

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-05

Last Updated

1999-05-11

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cse.iitk.ac.in/users/dsrkg/cs210/html/sortingpage.html

Edit

You may edit this entry if you have an account.

Ghosh - Merge Sort

Recommendation

Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. K. Ghosh

Institution

Indian Institute of Technology, Kanpur

Project

Ghosh's Collection

Works

Yes

Description

Two AVs available. Mergesort I shows standard bar swapping, but it also has a second array that shows the part that has been sorted and will be merged. Mergesort II shows step by step how the algorithm works. There are also explanatory pages along with the two AVs.

Evaluation

In combination, the two AVs do a good job of explaining mergesort. Each AV on its own has weaknesses. Mergesort I is a pure animation, but the second array makes this relatively clear. Despite the garish color scheme, Heapsort II almost a good visualization. The explanations for what is going on are fairly clear, with a step-by-step progression under user control. The problems are that the animation speed (each step is a mini-animation) is too slow, without any speed control, and the message about what is actually happening gets clobbered at the end of the step. So while the user can control the step progression, within the step there is no sense of control.

Step Control; Animation; Random Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-15

Last Updated

2001-08-12

Topic

Community

Average rating:	1.0
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/IteratedMergeSort.html

Edit

You may edit this entry if you have an account.

Trakla - Merge Sort

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Trakla2

Works

Yes

Description

Two versions of Merge are available: One labeled "iterative" and one labeled "recursive". User works through an exercise of swapping elements between the array and an auxilliary array to demonstrate proficiency at the mechanics of mergesort.

Evaluation

As an exercise, this is too tedious, and the directions are unclear. The recursive version makes no sense at all. Stepping through the "model answer" for the iterative version helps demonstrate how Merge Sort works, but it is not particularly intuitive.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.princeton.edu/courses/archive/spr09/cos226/demo/ah/MergeSort.html

Edit

You may edit this entry if you have an account.

Merge sort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

BSD-like

Language

English

Author

Alejo Hausner

Institution

Princeton University

Project

Gawain

Works

Yes

Description

Shows a simple bar-swap visualization for Mergesort.

Evaluation

No explanation for the algorithm is given. You just see bars swapping around.

Animation; Step Control

Lecture Aid

Screenshots

Videos

References

This link takes you to a page that has some explanation on Mergesort and how to use the AV. Just click on "run" or "step" to advance the algorithm. "Init" will reinitialize the AV with a new set of random values.

First Visited

2006-11-07

Last Visited

2009-08-17

Last Updated

1999-02-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.princeton.edu/~ah/alg_anim/version1/MergeSort.html

Edit

You may edit this entry if you have an account.

Merge sort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Alejo Hausner

Institution

Princeton University

Project

Works

Yes

Description

Bar swapping with continuous operation. Includes speed control, pause button, and zoom control. Shows how many "events" have taken place, somewhat like an AlgorithmSimulation.

Evaluation

Absolutely no explanation of what's occurring, and something about the animation makes it hard to follow what's even happening there.

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

1996-06-23

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.duke.edu/education/courses/cps130/fall99/animations/merge.html

Edit

You may edit this entry if you have an account.

Merge Example

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Language

English

Author

Institution

Duke University

Project

Works

Unavailable

Description

Link has been lost.

Evaluation

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

1999

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.toronto.edu/~neto/teaching/238/16/mergesort.html

Edit

You may edit this entry if you have an account.

MergeSort demo with comparison bounds

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

David Neto

Institution

University of Toronto

Project

Works

Description

Does not work.

Evaluation

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

1996

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://homepages.dcc.ufmg.br/~dorgival/applets/SortingPoints/SortingPoints.html

Edit

You may edit this entry if you have an account.

Animation of Sorting Algorithms - Merge Sort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Dorgival Olavo Guedes Neto

Institution

Universidade Federal de Minas Gerais

Project

Works

Yes

Description

No explanation of what is taking place. Another bar-swapping animation (although the "bars" are dots at different heights). Speed control.

Evaluation

Even the slowest speed is too fast to understand what's going on.

Animation

Comparison

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-05

Last Updated

1998-02-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/MSort.html

Edit

You may edit this entry if you have an account.

Java Applets Centre - Merge Sort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. Mukundan

Institution

University of Canterbury

Project

Java Applets Centre

Works

Yes

Description

Bar-swapping with only continuous mode operation (no speed control). Only randomly-generated data sets, but you may choose the size of the data set.

Evaluation

Very little to recommend this application. Lack of speed control or stepwise operation is a major flaw, and there is no explanation for what bars are being compared (only swaps are shown).

Animation Only; Random Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-05

Last Updated

2006

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.cmu.edu/~jaharris/applets/sorting/merge/mergesort.htm

Edit

You may edit this entry if you have an account.

Merge Sort Applet

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

James Harrison

Institution

Carnegie-Mellon University

Project

Works

Yes

Description

Simple bar-swapping animation for merge sort.

Evaluation

You can't really understand what is going on from just watching bars swap.

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

1996-10-11

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.geocities.com/SiliconValley/Network/1854/Sort1.html

Edit

You may edit this entry if you have an account.

Animated Algorithms - Merge Sort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Non-OSI Open Source

Language

English

Author

David M. Howard

Institution

None

Project

Works

Yes

Description

Bar-swapping, four different data sets, no speed control or stepwise operation. Shows number of operations a la AlgorithmSimulation.

Evaluation

Just another bar-swapping animation. The usual critiques apply: lack of speed control or even a pause button make this almost useless.

Comparison

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

1998-10-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://mainline.brynmawr.edu/Courses/cs206/spring2004/WorkshopApplets/Chap06/MergeSort/MergeSort.html

Edit

You may edit this entry if you have an account.

Lafore's Merge Sort

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Robert LaFore

Institution

None

Project

LaFore's Book

Works

Yes

Description

Has two data sets, stepwise and continuous operation, pointers which show what is being acted on, and descriptions of what's occurring.

Evaluation

A bar-swapping animation done well. Gives decent explanations of what's taking place. Unfortunately, all you see is pointers to the bars being swapped. There is no real sense of what mergsort is about (sorting two sublists and merging them together).

Teaching the Concept

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2008-06-16

Last Updated

2002

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://haegar.fh-swf.de/AlgoDat/sorts/MergeSort/mergesort.html

Edit

You may edit this entry if you have an account.

MergeSort demo

Recommendation

Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

David Neto

Institution

University of Applied Sciences

Project

Works

Yes

Description

Shows recursive descent into subsets of the data. Has multiple data sets, stepwise and continuous operation, speed control, and rewind.

Evaluation

Better than just plain bar-swapping! Actually shows how the algorithm works.

Teaching the Concept

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

1996

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm

Edit

You may edit this entry if you have an account.

Sorting Algorithms - Mergesort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Hans Werner Lang

Institution

University of Applied Sciences

Project

Works

Description

Does not appear to work.

Evaluation

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

2006-06-02

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cic.unb.br/docentes/arcela/lcmm/disciplinas/ed2006.1/t3/0523640/index.html

Edit

You may edit this entry if you have an account.

MergeSort - Brasília

Recommendation

Not Recommended

Link

Delivery Method

License

Language

English

Author

Institution

Universidade de Brasília

Project

Works

Unavailable

Description

Server said "Forbidden".

Evaluation

Screenshots

Videos

References

First Visited

2006-11-07

Last Visited

2007-04-10

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.niemueller.de/software/palm/unisorter/

Edit

You may edit this entry if you have an account.

UniSorter

Recommendation

Unrated

Link

Delivery Method

PalmOS Application

License

GPL

Language

English

Author

Tim Niemueller

Institution

RWTH Aachen

Project

UniSorter

Works

Description

PalmOS-based sorting visualization. Includes several sorts.

Evaluation

Unknown; no PalmOS device available for testing.

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2007-04-03

Last Updated

2005-10-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://gustavus.edu/academics/mcs/max/concabs/applets/sort/

Edit

You may edit this entry if you have an account.

Card Sorting Simulations -- Mergesort

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Language

English

Author

Max Hailperin

Institution

Gustavus Adolphus College

Project

Works

Yes

Description

This is an example of a "virtual manipulative" in that it purposely mimics implementing merge sort using the physical manipulative of a deck of cards. The user moves one card at a time between "destination," "source," and "discard" piles.

Evaluation

A good idea within its intended purpose. It is a little awkward because it can be difficult to understand what you are supposed to do until you catch on. This AV focuses on the details of how values are moved around, which can be helpful for understanding how the merge operation works. Unfortunately, the restriction to three "piles" makes it difficult to grasp how the sublists are sorted. It can also be a little difficult to understand what you are supposed to do until you catch on. A variant on this AV that focussed just on merge might do a good job of explaining merge. But I think its really hard to understand Mergesort from this presentation. This applet is paired with a similar implementation for Selection Sort, with one purpose being to see how Mergesort is far more efficient than Selection Sort. The Mergesort implementation suffers from a similar problem as does the Selection Sort implementation: To follow the "virtual manipulative" model that mimics moving cards around, it is not implementing the "real" algorithm that the computer would implement. Instead, its been altered a bit to fit into 3 piles of cards. Again, you get the right feel for merging, but its not so accurate a portrayal of the interrelationships between the various sublists.

Lecture Aid

Screenshots

Videos

References