Lecture Data Structures: Lesson 45 provide students with knowledge about divide and conquer; binary search; mergesort; splits the list in half; mergesorts the two halves; merging animation; mergesort the right half; merge sort and linked lists; . | Lecture Data Structures Dr. Sohail Aslam Divide and Conquer What if we split the list into two parts 10 12 8 4 2 11 7 5 Divide and Conquer Sort the two parts 10 4 12 8 10 8 12 4 2 11 5 7 11 5 Divide and Conquer Then merge the two parts together 24 48 10 5 12 7 82 10 5 11 7 11 12 Analysis To sort the halves n 2 2 n 2 2 To merge the two halves n So for n 100 divide and conquer takes 100 2 2 100 2 2 100 2500 2500 100 5100 n2 10 000 Divide and Conquer Why not divide the halves in half The quarters in half And so on . . . When should we stop At n 1 Divide and Conquer Recall Binary Search Search Search Search Divide and Conquer Sort Sort Sort Sort Sort Sort Sort Divide and Conquer Combine Combine Combine Mergesort Mergesort is a divide and conquer algorithm that does exactly that. It splits the list in half Mergesorts the two halves Then merges the two sorted halves together Mergesort can be implemented recursively Mergesort The mergesort algorithm involves three steps If the number of items to sort is 0 or 1 return Recursively sort the first and second halves separately Merge the two sorted halves into a sorted group Merging animation 4 8 10 12 2 5 7 11 2 Merging animation 4 8 10 12 2 5 7 11 2 4 Merging animation 4 8 10 12 2 5 7 11 2 4 5 Merging 4 8 10 12 2 5 7 11 2 4 5 7 Mergesort Split the list in half. Mergesort the left half. 10 4 8 12 11 2 7 5 Split the list in half. Mergesort the left half. 10 4 8 12 Split the list in half. Mergesort the left half. 10 4 Mergesort the right. 10 4 Mergesort 10 4 8 12 11 2 7 5 10 4 8 12 Mergesort the right half. Merge the two halves. 10 4 10 4 8 12 Merge the two halves. 8 12 Mergesort 10 4 8 12 11 2 7 5 Merge the two halves. 10 4 84 10 8 12 Mergesort the right half. Merge the two halves. 10 4 10 4 8 12 Mergesort Mergesort the right half. 4 8 10 12 11 2 7 5 11 2 7 5 11 2 11 2 Mergesort Mergesort the right half. 4 8 10 12 11 2 7 5 11 2 11 2 7 5 11 2 11 2
