14. Merge sort
14 May 2020 | Data structure_1
Introduction
- Merge Sort is the fastest algorithm we are going to be analyzing. (Fastest on average, quicksort is technically faster, but has the problem of the n^2 worst case). It has a way of dividing the data up like in quick sort, except that it doesn’t require selecting a pivot point to get the nlogn run times.
Why is it Important?
- Merge sort is one of the fastest comparison sorts. It runs at nlogn for all run times, making it reliably fast at splitting up and sorting data.
Lesson Notes
-
Merge sort is one of the fastest algorithms for sorting using comparisons. However, this also makes it quite complex as well. It uses the divide and conquer methodology used in the quick sort algorithm.
-
It works by dividing up the data in to smaller and smaller chunks. It then recombines them in to a sorted algorithm.
-
The array breaks down the data until it is in single unit subarrays. It then recombines them using cursors that only have touch each element once for each combination.
-
So each level is going to be at most n amount of “touches”. Because of the way it breaks up the algorithm, it has logn amount of levels.
-
This means that is will always run at nlogn timing, as there is no way to break it up worse than logn levels. So it will be n amount of touches per level multiple by logn amount of levels, giving us an even nlogn no matter what array comes in.
-
Best Time: Ω(nlogn) : The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn
-
Average Time: Θ(nlogn) : The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn
-
Worst Time: O(nlogn) The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn
Comparison
Quiz
Introduction
- Merge Sort is the fastest algorithm we are going to be analyzing. (Fastest on average, quicksort is technically faster, but has the problem of the n^2 worst case). It has a way of dividing the data up like in quick sort, except that it doesn’t require selecting a pivot point to get the nlogn run times.
Why is it Important?
- Merge sort is one of the fastest comparison sorts. It runs at nlogn for all run times, making it reliably fast at splitting up and sorting data.
Lesson Notes
-
Merge sort is one of the fastest algorithms for sorting using comparisons. However, this also makes it quite complex as well. It uses the divide and conquer methodology used in the quick sort algorithm.
-
It works by dividing up the data in to smaller and smaller chunks. It then recombines them in to a sorted algorithm.
-
The array breaks down the data until it is in single unit subarrays. It then recombines them using cursors that only have touch each element once for each combination.
-
So each level is going to be at most n amount of “touches”. Because of the way it breaks up the algorithm, it has logn amount of levels.
-
This means that is will always run at nlogn timing, as there is no way to break it up worse than logn levels. So it will be n amount of touches per level multiple by logn amount of levels, giving us an even nlogn no matter what array comes in.
-
Best Time: Ω(nlogn) : The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn
-
Average Time: Θ(nlogn) : The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn
-
Worst Time: O(nlogn) The same algorithm is applied no matter what type of array comes in. This means it will always be nlogn
Comments