Merge Sort Algorithm
By Logan Ho
History of the Merge
Sort Algorithm-
The merge sort algorithm is
said to be one of the earliest sorting algorithms created. An intelligent man named John von Neumann in
1945 invented it. How intelligent you
ask? Lets simply say that by the age of
six, he could divide eight digit numbers in his head. John von Neumann was born on December 28, 1903 in Budapest
Hungary, and later died on February 8, 1957 in Washington D.C. Although he may have seemed to live a short
life, he made many accomplishments.
Neumann was a great mathematician who created other great works such as
linear programming, the automata theory, and the game theory. Aside from the various theories he created,
he helped build one of the first electronic computers called the ENIAC.
From the point of view of von Neumann's
contributions to the field of computing, including the application of his
concepts of mathematics to computing, and the application of computing to his
other interests such as mathematical physics and economics …there is no doubt
that his insights into the organization of machines led to the infrastructure
which is now known as the "von Neumann Architecture". – J.A.N Lee
The Code for the Merge Sort
Algorithm-
The code for the merge sort algorithm has two methods to
it. It has one method called
“mergesort” that recursively calls itself and another method called
“merge”. First, the mergesort method
recursively calls upon itself dividing the unsorted array into smaller pieces
until there is only one item per piece.
After it has broken down the array, it then calls the merge method,
which compares an item from one piece to another item from another piece and
merges them together in order. It keeps
on merging and sorting the pieces together until it becomes one array and the
recursion returns to its base method.
This algorithm may be better understood in java.
The Merge Sort Code –by Carrano and Prichard.
Big-O Analysis of the
Merge Sort Algorithm-
P. Brachmann introduced the
big-O notation in 1894. The Big-O notation
efficiently measures the amount of time it takes an algorithm in relation to
the size of its problem. The big O
notation for the merge sort algorithm is an O (n * log n). Unlike an O (n) notation, which its time
increases linearly with its size, the O (n * log n) time increases more rapidly
as its size increases. But on the other
hand, unlike the O (n^2) notation, which its time increases rapidly with its
size, the O (n * log n) increases slower.
The big O notation is also used to measure the average case and worst
case of an algorithm. According to Carrano
and Prichard, “worst-case analysis considers the maximum amount of work an
algorithm will require on a problem of a given size, while average-case
analysis considers the expected amount of work that it will require.”
A Table Comparing Growth-Rate of the Common
Functions
Function
|
10 |
100 |
1,000 |
10,000 |
100,000 |
1,000,000 |
|
1 (Constant) |
1 |
1 |
1 |
1 |
1 |
1 |
|
log2 N |
3 |
6 |
9 |
13 |
16 |
19 |
|
N (Linear) |
10 |
100 |
1,000 |
10,000 |
100,000 |
1,000,000 |
|
N * log2 N |
30 |
664 |
9,965 |
105 |
106 |
107 |
|
N2 (Quadratic) |
102 |
104 |
106 |
108 |
1010 |
1012 |
|
N3 (Cubic) |
103 |
106 |
109 |
1012 |
1015 |
1018 |
|
2N (Exponential) |
103 |
1030 |
10301 |
103,010 |
1030,103 |
10301,030 |
By Carrano and Prichard
Performance
of the Merge Sort Algorithm-
The
merge sort algorithm is a divide and conquer algorithm. Divide and conquer is based on the idea that
sometimes problems are too big to be solved, so they need to be broken down
into smaller parts then pieced together again.
It is easier to solve a large problem in smaller pieces then to solve it
as a whole. It is like building a car. One section works on the door, while the
other works on the engine and slowly all the parts are put together to create a
whole automobile. This is much simpler
then building the door and the engine at the same time, which is a bigger task
to accomplish. The merge sort is used
in many different situations. Some
situations include sorting names in a file, sorting phone numbers for a phone
book, sorting test scores from highest to lowest, and many more. The use of the algorithm depends on the
problem being solved and its size.
Divide and Conquer in simpler terms
1.
“Divide” the problem size
into more comprehendible pieces.
2. “Conquer” or resolve the smaller pieces recursively.
3. Finally put the pieces back together to create the final
solution
Comparison and Contrast
of the Merge Sort Algorithm against other sorting Algorithms-
As the battle rages on
determining which sorting algorithm is the fastest, merge sort has shown to be
one of the best. Speed of the bubble,
selection, and insertion sort begin to decrease as the problem size increases, making
the merge sort more efficient with larger size problems. Like
the merge sort, the quick sort has a similar big O notation, O (n*log n), as
the merge but in average cases is quicker.
However, in its worst cases, which are if the algorithm were to work at
its maximum capacity, the merge sort is much faster than the quick sort. Another disadvantage of the merge sort is the
need of a temporary array similar in size as the one being sorted. This
causes the merge sort to use up more memory because more storage is needed for the
second array. On the other hand, there
is also the heap sort algorithm. Like the
merge sort and quick sort it has a big O of O (n * log n) for its average case
and a O (n * log n) for its worst case like the merge. Although the merge, quick, and heap sort
have similar average cases, the heap sort builds a “heap” rather then using the
“divide and conquer” strategy, which performs recursively. One great advantage of the merge sort is
that you can easily merge two segments together. Unlike other sorting algorithms, which only can work with what is
in the internal memory, the merge sort is a great external file sorter, meaning
if the file being sorted is too great to fit into the internal memory, the
merge sort can work with external files to transfer data in and out of the internal
memory. Although the merge sort may
have its flaws and advantages, over all, it is one of the best sorting
algorithms in all different types of cases and situations.
Bibliography-
Carrano,
Frank M., Janet J. Prichard. Data Abstraction and Problem Solving with
Java. New York: Addison Wesley Longman, Inc., 2001.
Cordy, James R. http://www.cs.queensu.ca/home/cordy/cisc101/
Eppstein, David. http://www.ics.uci.edu/~eppstein/161/960118.html.
Lee, J.A.N. http://ei.cs.vt.edu/~history/VonNeumann.html
Whaley, Tom. http://home.wlu.edu/~whaleyt/classes/parallel/topics/dnc/dnc.html