[go: up one dir, main page]
Scribd
Upload
21 views26 pages

Slide 10

These are the Java algorithm lessons that we're studying them at university.

Uploaded by

farrokhisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views26 pages

Slide 10

These are the Java algorithm lessons that we're studying them at university.

Uploaded by

farrokhisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 26

Algorithm

Merge Sort

► Merge sort is yet another sorting algorithm that falls under the category of
Divide and Conquer technique. It is one of the best sorting techniques that
successfully build a recursive algorithm.
Divide and Conquer Strategy

► In this technique, we segment a problem into two halves and solve


them individually. After finding the solution of each half, we merge
them back to represent the solution of the main problem.
► Suppose we have an array A, such that our main concern will be to sort
the subsection, which starts at index p and ends at index r,
represented by A[p..r].
Divide

► If assumed q to be the central point somewhere in between p and r,


then we will fragment the subarray A[p..r] into two
arrays A[p..q] and A[q+1, r].
Conquer

► After splitting the arrays into two halves, the next step is to conquer. In
this step, we individually sort both of the subarrays A[p..q] and A[q+1,
r]. In case if we did not reach the base situation, then we again follow
the same procedure, i.e., we further segment these subarrays followed
by sorting them separately.
Combine

► As when the base step is acquired by the conquer step, we


successfully get our sorted subarrays A[p..q] and A[q+1, r], after which
we merge them back to form a new sorted array [p..r].
Merge Sort algorithm

► The MergeSort function keeps on splitting an array into two halves


until a condition is met where we try to perform MergeSort on a
subarray of size 1, i.e., p == r.
► And then, it combines the individually sorted subarrays into larger
arrays until the whole array is merged.
Continued…

► Here we called MergeSort(A, 0, length(A)-1) to sort the complete


array.
► As you can see in the image given below, the merge sort algorithm
recursively divides the array into halves until the base condition is met,
where we are left with only 1 element in the array. And then, the
merge function picks up the sorted sub-arrays and merge them back
to sort the entire array.
The merge step of Merge Sort

► Mainly the recursive algorithm depends on a base case as well as its


ability to merge back the results derived from the base cases. Merge
sort is no different algorithm, just the fact here the merge step
possesses more importance.
► To any given problem, the merge step is one such solution that
combines the two individually sorted lists(arrays) to build one large
sorted list(array).
► The merge sort algorithm upholds three pointers, i.e., one for both of
the two arrays and the other one to preserve the final sorted array's
current index.
Continued…

► Did you reach the end of the array?


► No:
► Firstly, start with comparing the current elements of both the arrays.
► Next, copy the smaller element into the sorted array.
► Lastly, move the pointer of the element containing a smaller element.
► Yes:
► Simply copy the rest of the elements of the non-empty array
Merge( ) Function Explained
Step-By-Step
► Consider the following example of an unsorted array, which we are
going to sort with the help of the Merge Sort algorithm.
► A= (36,25,40,2,7,80,15)
► Step1: The merge sort algorithm iteratively divides an array into equal
halves until we achieve an atomic value. In case if there are an odd
number of elements in an array, then one of the halves will have more
elements than the other half.
► Step2: After dividing an array into two subarrays, we will notice that it
did not hamper the order of elements as they were in the original
array. After now, we will further divide these two arrays into other
halves.
► Step3: Again, we will divide these arrays until we achieve an atomic
value, i.e., a value that cannot be further divided.
Continued…

► Step4: Next, we will merge them back in the same way as they were
broken down.
► Step5: For each list, we will first compare the element and then
combine them to form a new sorted list.
► Step6: In the next iteration, we will compare the lists of two data
values and merge them back into a list of found data values, all placed
in a sorted manner.
Analysis of Merge Sort:

► Let T (n) be the total time taken by the Merge Sort algorithm.
► Sorting two halves will take at the most 2T time.
► When we merge the sorted lists, we come up with a total n-1
comparison because the last element which is left will need to be
copied down in the combined list, and there will be no comparison.
► Thus, the relational formula will be
Continued…

► But we ignore '-1' because the element will take some time to be
copied in merge lists.
Continued…

► Put 2 equation in 1 equation


Continued…

► Putting 4 equation in 3 equation


From Stopping Condition:
Continued…

► Apply log both sides:


From 6 equation
Complexity:

► Best Case Complexity: The merge sort algorithm has a best-case time
complexity of O(n*log n) for the already sorted array.
► Average Case Complexity: The average-case time complexity for the
merge sort algorithm is O(n*log n), which happens when 2 or more
elements are jumbled, i.e., neither in the ascending order nor in the
descending order.
► Worst Case Complexity: The worst-case time complexity is
also O(n*log n), which occurs when we sort the descending order of
an array into the ascending order.
► Space Complexity: The space complexity of merge sort is O(n).
Merge Sort Applications

► The concept of merge sort is applicable in the following areas:


• Inversion count problem
• External sorting
• E-commerce applications
?

You might also like