2.7.1 Two Way MergeSort - Iterative method
Introduction to Merge Sort
In this section, the speaker introduces the topic of merge sort and explains what merging is.
What is Merging?
- Merging is a process of combining two sorted lists into a single sorted list.
- The two lists can be in an array or linked list data structure.
- The procedure for merging involves comparing elements from each list and copying the smaller element to a third list.
- This process continues until one of the lists has no more elements remaining.
- The resulting list is sorted.
Time Complexity of Merging
- The time complexity for merging two lists with M and N elements respectively is Theta(M+N).
- This time complexity accounts for the time taken to move data from one list to another during the merging process.
Procedure for Merging in Code
- The algorithm for merging takes two lists as input and returns a merged, sorted list.
- The procedure involves initializing index pointers for each input list and a third output list.
- Elements are compared between the input lists, with the smaller element being copied to the output list.
- Index pointers are incremented accordingly until one of the input lists has no more elements remaining.
- Any remaining elements in either input list are then copied to the output list.
Merging Multiple Lists
In this section, the speaker explains how to merge multiple lists together using a comparison method. They also discuss different patterns of merging and explain two-way merging.
Comparing and Merging Lists
- To merge multiple lists, compare the first element of each list and copy the smallest one into a final list.
- Repeat this process for each subsequent element in each list until all elements have been merged.
- This method can be used to merge any number of lists together, with four-way merging being an example of merging four lists at once.
- Two-way merging is more commonly used and involves taking pairs of lists at a time and merging them.
Two-Way Merge Sort
The speaker discusses two sorting methods - two-way merge sort and quicksort - explaining the differences between them.
Two-Way Merge Sort
- Two-way merge sort involves taking pairs of elements from an unsorted array, sorting them, then merging them into a sorted array.
- This process is repeated until all elements are sorted.
- If there are an odd number of elements in the array, the last element will not have a pair to be merged with and will simply be added to the sorted array later on.
Sorting Using Merge Process
The speaker explains how to use the merge process to sort an unsorted array.
Sorting Using Merge Process
- To sort an unsorted array using the merge process, assume that each element in the array is its own list containing only one element (since single-element lists are already sorted).
- Take pairs of these single-element lists and merge them into new sorted lists.
- Repeat this process until all single-element lists have been merged into one sorted list.
- Keep in mind that the merged lists should be stored in a separate array from the original unsorted array.
Merging Lists
In this section, the speaker explains how to merge multiple lists into a single sorted list using the merge sort algorithm.
Merge Sort Algorithm
- The speaker starts with four lists, each with two elements.
- The smaller lists are merged first, resulting in a list of four elements.
- The process is repeated until there is only one list left.
- The number of passes required for merging all the elements is log base 2 of n, where n is the number of elements.
- Total time complexity for merging all the elements is O(n log n).
Analysis of Merge Sort Algorithm
In this section, the speaker analyzes how much work is done in each pass and how many passes are required to merge all the elements.
Work Done in Each Pass
- In each pass, n/2 comparisons are made where n is the number of elements.
Number of Passes Required
- The number of passes required for merging all the elements is log base 2 of n, where n is the number of elements.