Merge Sort - Data Structures and Algorithm Lecture Note PDF

Faculty of Information Technology University of Moratuwa BSc(Hons) in Information Technology BSc(Hons) in Artificial Intelligence IN 1111 - Data Structures and Algorithm part...

Faculty of Information Technology University of Moratuwa BSc(Hons) in Information Technology BSc(Hons) in Artificial Intelligence IN 1111 - Data Structures and Algorithm part 2 Level 2 - Semester 2 Lecture Note 01 Merge Sort 1.1 What is Merge Sort ? Merge Sort is a popular sorting algorithm that follows the divide-and-conquer paradigm. It works by dividing the unsorted list into 'n' sub-lists, each containing one element, and then repeatedly merging sub-lists to produce new sorted sub-lists until there is only one sub-list remaining, which is the sorted list Here's a high-level description of the Merge Sort algorithm Divide: Divide the unsorted list into 'n' sub-lists, each containing one element Conquer: Repeatedly merge sub-lists to produce new sorted sub-lists until there is only one sub-list remaining Merge: Merge two sub-lists into a single sorted sub-list. This process is repeated until there is only one sub-list remaining, which is the sorted list The key operation in Merge Sort is the merging of two sorted sub-lists. The merge operation compares elements from two sub-lists and places them in sorted order. 1.2 Why Merge Sort ? Merge Sort is considered advantageous over other sorting algorithms in certain scenarios due to its characteristics and performance. Here are some reasons why Merge Sort is preferred in certain situations Stability: Merge Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output. This property is crucial in situations where preserving the initial order of equal elements is important Predictable Performance: Merge Sort has a consistent, predictable performance with a time complexity of O(n log n) in the worst, average, and best cases. This makes it suitable for scenarios where a reliable and efficient sorting algorithm is required across various input data distributions External Sorting: Merge Sort is particularly well-suited for external sorting scenarios where data is too large to fit into memory. It can efficiently handle large datasets by reading and writing smaller chunks of data at a time Parallelization: Merge Sort can be easily parallelized, taking advantage of multiple processors or cores to enhance performance. Each sub-list can be sorted independently, and the sorted sub-lists can then be efficiently merged in parallel Consistent Memory Usage: Merge Sort typically uses a consistent amount of additional memory regardless of the input data size. This makes it more memory-efficient than some other algorithms, such as quicksort, in situations where memory usage is a concern Ease of Implementation: Merge Sort has a straightforward and modular implementation, making it easier to understand and maintain. The divide-and-conquer approach lends itself well to recursive implementations. While Merge Sort has these advantages, it's important to consider other sorting algorithms like Quicksort, Heapsort, or insertion sort, depending on the specific requirements and characteristics of the data. For example, quicksort may be faster than mergesort for small datasets or datasets with a high degree of pre-sortedness. 1.3 Decomposition The MergeSort repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1 This can be achieved by applying recursion until it stops. 1.4 Merging The merge step is the solution to the simple problem of merging two sorted lists(arrays) to build one large sorted list(array). The algorithm maintains three pointers, one for each of the two arrays and one for maintaining the current index of the final sorted array. 1.5 Code Our task is to merge two subarrays A[p..q] and A[q+1..r] to create a sorted array A[p..r]. So the inputs to the function are A, p, q and The merge function works as follows Create copies of the subarrays L