Merge Sort Algorithm for Efficient Sorting
"Explore the Divide and Conquer approach of Merge Sort for sorting arrays efficiently. Learn about the key processes like dividing the array, calling the function recursively, and merging sorted halves. Discover the relevance of Merge Sort in linked lists and its advantages over other nLogn algorithms like Heap Sort and Quick Sort. Get insights into practical implementations through pseudo-code examples and usage scenarios."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Sorting Algorithms Merge Sort
Merge Sort MergeSort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merg() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
Pseudo-code MergeSort(arr[], l, r) If r > l 1.Find the middle point to divide the array into two halves: middle m = (l+r)/2 2. Call mergeSort for first half: Call mergeSort(arr, l, m) 3. Call mergeSort for second half: Call mergeSort(arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
main() #include<iostream> using namespace std; void mergeSort(int*, int, int); void mergeArray(int*, int, int, int); int const n=6; void main() { } int arr[n]; for(int i=0; i<n; i++) cin>>arr[i]; mergeSort(arr, 0, n-1); system("pause");
void mergesort() void mergeSort(int *arr, int startIndex, int endIndex) { int mid=(startIndex+endIndex)/2; if(startIndex < endIndex) { mergeSort(arr, startIndex, mid); mergeSort(arr, mid+1, endIndex); mergeArray(arr, startIndex, endIndex, mid); } }
void mergeArray() void mergeArray (int *arr, int startIndex, int endIndex, int mid) { int i, j, k, tempArray[n]; i=startIndex; j=mid+1; k=startIndex; while(i<=mid && j<=endIndex) { if(arr[i] < arr[j]) { tempArray[k] = arr[i]; k++; i++; } else { tempArray[k] = arr[j]; k++; j++; } } while(i <= mid) { } while(j <= endIndex) { } for(i=startIndex; i<k; i++) { arr[i] = tempArray[i]; } } tempArray[k] = arr[i]; k++; i++; tempArray[k] = arr[j]; k++; j++;
Usage Merge Sort is useful for sorting linked lists in O(nLogn) time. Other nlogn algorithms like Heap Sort, Quick Sort (average case nLogn) cannot be applied to linked lists. Inversion Count Problem Used in External Sorting
