Understanding Merge Sort: A Brief Overview of an Earlier Sorting Algorithm

undefined
 
A BRIEF LOOK AT ONE OF THE EARLIER
SORTING ALGORITHMS
 
Merge Sort
 
History of the Merge Sort
 
Written around 1945
Commonly attributed to renown Hungarian-
American mathematician John von Neumann
One of the first sorting styles proposed for computers
Uses divide and conquer principles (recursively
breaking down a problem into smaller sub-
problems)
 
What does a merge sort look like?
 
 
Graphic courtesy of Wikimedia Commons
 
So what’s happening exactly?
 
The data is recursively broken down into smallest
possible subset (in this case, an individual number)
The first item in one subset is compared to the first
in the next subset
The smaller of the two is placed first in a new set,
then the second smallest etc.
Increasingly larger sorted sets are formed until the
final, fully sorted list is made by comparing one
sorted half of the data to the other sorted half
 
Let’s try our own merge sort
 
Here we have the months of the year, except somehow they were placed
out of order
 
First, divide the list into individual months
 
Now, compare the first two
 
March comes before November, so March will be
added to the new set first and then November second
 
Now compare the rest of the sets
 
Compare again
 
The first item in the first two groups are
compared and the earlier month is added to the
new set
 
Round 2
 
…and then the second item in the first group
is compared with the first item of the second
group
 
The newly sorted groups
 
Compare the first two groups…
 
Building the new set
 
And sorted
 
One final merge sort
 
Building the final set
 
Sort complete!
 
Class Demonstrati0n
 
Get eight volunteers to stand in a line at the front of
the classroom
Have each draw a number out of a hat
Perform a merge sort on the volunteers by
comparing their numbers and grouping accordingly
Alternatively, use height for sorting if that can be
done without hurting morale
 
Merge Sorts and Binary Trees
 
The merge sort algorithm
can be visualized using a
binary tree, where:
Each leaf node is one piece
of data
Going up one level
involves one merge
process
 
Image courtesy of Rashid Bin Muhammad at Kent
State University
 
Time Complexity
 
Best case: O(n)
When values are already sorted
Worst case: O(
n
 log 
n
 )
n
 operations / level * log 
n
 + 1 levels
When the data is unsorted/randomly arranged
Average case: O(
n
 log 
n
 )
The only stable O(
n 
log 
n
 ) sorting algorithm
 
Memory Requirements
 
Array implementation
Generally requires a second array to store the merged list
O( 
n 
) extra space
Linked list implementation
Can be done in place by changing list pointers
O( log 
n
 ) extra space [for recursion]
Recursive nature of algorithm requires extra memory
compared to a non-recursive algorithm
 
When should you use merge sort?
 
For linked lists
When wanting to avoid random access to data
If stability is desired
When using extra space is not a concern
 
References
 
http://www.cprogramming.com/tutorial/computers
ciencetheory/mergesort.html
http://www.sorting-algorithms.com/merge-sort
http://www.personal.kent.edu/~rmuhamma/Algorit
hms/MyAlgorithms/Sorting/mergeSort.htm
http://en.wikipedia.org/wiki/Merge_sort
Slide Note
Embed
Share

History of the Merge Sort, its principles of divide and conquer, and visual representations of how the algorithm works through comparisons and sorting steps. Includes a hands-on example of applying Merge Sort to reorder a list of months.


Uploaded on Sep 11, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Merge Sort A BRIEF LOOK AT ONE OF THE EARLIER SORTING ALGORITHMS

  2. History of the Merge Sort Written around 1945 Commonly attributed to renown Hungarian- American mathematician John von Neumann One of the first sorting styles proposed for computers Uses divide and conquer principles (recursively breaking down a problem into smaller sub- problems)

  3. What does a merge sort look like? Graphic courtesy of Wikimedia Commons

  4. So whats happening exactly? The data is recursively broken down into smallest possible subset (in this case, an individual number) The first item in one subset is compared to the first in the next subset The smaller of the two is placed first in a new set, then the second smallest etc. Increasingly larger sorted sets are formed until the final, fully sorted list is made by comparing one sorted half of the data to the other sorted half

  5. Lets try our own merge sort Here we have the months of the year, except somehow they were placed out of order November April October January June March February December September May July August

  6. First, divide the list into individual months

  7. Now, compare the first two March comes before November, so March will be added to the new set first and then November second

  8. Now compare the rest of the sets

  9. Compare again The first item in the first two groups are compared and the earlier month is added to the new set

  10. Round 2 and then the second item in the first group is compared with the first item of the second group

  11. The newly sorted groups

  12. Compare the first two groups

  13. Building the new set

  14. And sorted

  15. One final merge sort

  16. Building the final set

  17. Sort complete!

  18. Class Demonstrati0n Get eight volunteers to stand in a line at the front of the classroom Have each draw a number out of a hat Perform a merge sort on the volunteers by comparing their numbers and grouping accordingly Alternatively, use height for sorting if that can be done without hurting morale

  19. Merge Sorts and Binary Trees The merge sort algorithm can be visualized using a binary tree, where: Each leaf node is one piece of data Going up one level involves one merge process Image courtesy of Rashid Bin Muhammad at Kent State University

  20. Time Complexity Best case: O(n) When values are already sorted Worst case: O(n log n ) n operations / level * log n + 1 levels When the data is unsorted/randomly arranged Average case: O(n log n ) The only stable O(n log n ) sorting algorithm

  21. Memory Requirements Array implementation Generally requires a second array to store the merged list O( n ) extra space Linked list implementation Can be done in place by changing list pointers O( log n ) extra space [for recursion] Recursive nature of algorithm requires extra memory compared to a non-recursive algorithm

  22. When should you use merge sort? For linked lists When wanting to avoid random access to data If stability is desired When using extra space is not a concern

  23. References http://www.cprogramming.com/tutorial/computers ciencetheory/mergesort.html http://www.sorting-algorithms.com/merge-sort http://www.personal.kent.edu/~rmuhamma/Algorit hms/MyAlgorithms/Sorting/mergeSort.htm http://en.wikipedia.org/wiki/Merge_sort

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#