DSA- Merge Sort-a sorting technique.pptx

A sorting technique in DSA called merge sort. Merge Sort is explained briefly in the above ppt.

1. Merge Sort PRESENTATION BY: SANDEEP DAS, HIMANGSHU LAHKAR, RAHUL, DEBRAJ & GAURAV Algorithm

2. ‹#› The Merge Sort Algorithm o1. I ntroduction o3. Algorithm Steps o4. Example Illustration o5. Application of Merge Sort o2. Overview of Merge Sort o6. Advantages Over Other Sorting Algorithms 2

3. Introduction Brief explanation of sorting and its importance Introduction to the divide-and-conquer paradigm

4. Brief explanation of sorting and its importance A sorting algorithm is a step-by-step procedure for arranging elements in a specific order. The goal is to organize a collection of items into either ascending or descending order based on a defined comparison criterion. Sorting is crucial for optimizing search efficiency, enhancing user experience, facilitating algorithmic optimizations, and providing meaningful insights from data, making it a fundamental operation in computer science and data processing. ‹#›

5. Introduction to the divide-and-conquer paradigm ‹#› The divide and conquer paradigm is a problem-solving approach that involves breaking down a problem into smaller, more manageable parts, solving them individually, and then combining those solutions to solve the original problem. It typically consists of three steps: divide the problem into smaller sub problems, conquer by solving these sub problems recursively, and then combine the solutions of the sub problems to form the solution of the original problem. This strategy is widely used in various algorithms and computational tasks, such as sorting algorithms (like merge sort and quick sort) and algorithms for searching, optimization, and data processing.

6. ‹#› The Merge Sort Algorithm o1. Introduction o3. Algorithm Steps o4. Example Illustration o5. Application of Merge Sort o2. Overview of Merge Sort Advantages Over Other Sorting Algorithms o6. ‹#›

7. Overview of Merge Sort Explanation of why merge sort is a divide-and-conquer algorithm Basic introduction to the merge sort algorithm

8. Explanation of why merge sort is a divide-and-conquer algorithm Merge sort is a divide and conquer algorithm because it breaks down the sorting process into smaller, more manageable parts. It divides the unsorted list into smaller sub lists until each sub list consists of only one element. Then, it conquers by merging these smaller sorted lists back together in a sorted manner until the entire list is sorted. This divide-and-conquer approach simplifies the sorting process and helps achieve efficient sorting of large datasets. ‹#›

9. Basic introduction to the merge sort algorithm Merge sort is defined as a sorting algorithm that works by dividing an array into smaller sub arrays, sorting each sub array, and then merging the sorted sub arrays back together to form the final sorted array. In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted. Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted sub arrays are merged into one sorted array. ‹#› ‹#›

10. ‹#› The Merge Sort Algorithm o1. Introduction o3. Algorithm Steps o4. Example Illustration o5. Application of Merge Sort o2. Overview of Merge Sort Advantages Over Other Sorting Algorithms o6. ‹#›

11. Algorithm Steps Dividing Repeatedly divide the array into two halves until each subarray contains a single element Conquering Treat single-element subarrays as sorted Merging Combine sorted subarrays to produce a larger sorted array ‹#›

12. Algorithm Merge sort is a divide-and-conquer algorithm that works with the following steps: Step 1 − if it is only one element in the list it is already sorted, return. Step 2 − divide the list recursively into two halves until it can no more be divided. Step 3 − merge the smaller lists into new list in sorted order. This algorithm ensures that the elements are sorted by recursively dividing the array into smaller parts, sorting them, and then merging them back together. ‹#› ‹#›

13. Algorithm MergeSort (a, beg, end) 1. If beg < end Then 2. mid (beg+ end)/2 3. MergeSort (a, beg, end) 4. MergeSort (a, beg, mid) 5. MergeSort (a, mid + 1, end) ‹#› ‹#›

14. Algorithm Merge (a, beg, mid, end) 1. b = Create array b of same size a 2. i = beg, j = mid + 1, k = beg 3. While i <= mid and j <= end 4. If a[i] > a[j] Then 5. b[k++] = a[j++] 6. Else 7. b[k++] = a[i++] 8. While i <= mid 9. b[k++] = a[i++] 10. While j <= end 11. b[k++] = a[j++] 12. Loop from i = start to end 13. a[i] = b[i] ‹#› ‹#›

15. ‹#› The Merge Sort Algorithm o1. Introduction o3. Algorithm Steps o4. Example Illustration o5. Application of Merge Sort o2. Overview of Merge Sort Advantages Over Other Sorting Algorithms o6. ‹#›

16. Example Illustration Walk through a simple example of applying merge sort to a small array Merge sort program in C along with the output

17. ‹#› Illustration Lets consider an array  arr[ ] = {38, 27, 43, 10} Initially divide the array into two equal halves: ‹#›

18. ‹#› These sub arrays are further divided into two halves. Now they become array of unit length that can no longer be divided and array of unit length are always sorted. ‹#›

19. ‹#› These sorted sub arrays are merged together, and we get bigger sorted sub arrays. ‹#›

20. ‹#› This merging process is continued until the sorted array is built from the smaller sub arrays. The following diagram shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}.  ‹#›

21. ‹#›

22. ‹#›

23. ‹#› Output

24. ‹#› The Merge Sort Algorithm o1. Introduction o3. Algorithm Steps o4. Example Illustration o5. Application of Merge Sort o2. Overview of Merge Sort Advantages Over Other Sorting Algorithms o6. ‹#›

25. Application of Merge Sort Real-world scenarios where merge sort is applicable

26. Real-world scenarios where merge sort is applicable Merge Sort is applicable in several real-world scenarios where a stable and efficient sorting algorithm is needed. Here are some specific examples: 1. External Sorting in Database Systems: Merge Sort is often used for external sorting in database systems where datasets are too large to fit into memory. It efficiently handles sorting large amounts of data stored on external storage devices like hard drives. 2. Flight Schedule Sorting:  In the aviation industry, Merge Sort can be applied to sort flight schedules. It ensures that flights are arranged in order of departure times and maintains stability when additional criteria, such as airline or destination, are considered. ‹#›

27. ‹#› 3. File System Sorting: File systems, especially in scenarios where directories or file listings need to be sorted, can benefit from Merge Sort. Its efficiency in handling large datasets and stability make it a suitable choice. 4. Live Sorting in Streaming Applications: Merge Sort is useful in scenarios where data is continuously added or streamed in real-time. Its ability to handle live sorting, along with its stable nature, makes it applicable in streaming applications.  5. Business and Financial Applications: In financial systems, where transactions or records need to be sorted based on various criteria, Merge Sort can be applied. Its stability is crucial for maintaining the order of equal elements, such as transactions with the same timestamp. ‹#›

28. ‹#› The Merge Sort Algorithm o1. Introduction o3. Algorithm Steps o4. Example Illustration o5. Application of Merge Sort o2. Overview of Merge Sort Advantages Over Other Sorting Algorithms o6. ‹#›

29. Advantages Over Other Sorting Algorithms Highlight the advantages of merge sort, such as its stability, efficiency, and suitability for large datasets Its drawbacks

30. The advantages of merge sort, such as its stability, efficiency and suitability for large datasets Merge Sort offers several advantages that make it a popular choice in various scenarios. Here are the key advantages of Merge Sort:  1. Stability: Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements in the sorted output. This stability is crucial in applications where maintaining the original order of equivalent elements is important, such as sorting records based on multiple criteria. 2. Efficiency for Large Datasets: Merge Sort has a predictable and efficient time complexity of O(n log n). This linearithmic time complexity ensures that the algorithm maintains good performance even as the dataset size increases. It is particularly well-suited for sorting large datasets, making it an efficient choice in scenarios where scalability is crucial.  ‹#› ‹#›

31. 3. Divide-and-Conquer Strategy: The divide-and-conquer nature of Merge Sort allows it to break down complex sorting problems into smaller, more manageable sub-problems. This approach enhances the algorithm's scalability and adaptability, making it suitable for a wide range of dataset sizes and distributions. 4. External Sorting: Merge Sort is effective for external sorting, where data sets are too large to fit into the computer's main memory. Its ability to efficiently handle sorting on external storage devices, such as hard drives, is a practical advantage in real-world applications dealing with massive datasets. 5. Simplicity and Clarity: Merge Sort is conceptually simple and clear, making it easy to understand and implement. Its straightforward design contributes to its reliability and maintainability in various applications. ‹#› ‹#›

32. Its Drawbacks Merge sort has drawbacks, including its non-adaptive nature that doesn't exploit partially sorted input, the additional space required for merging, and the inefficiency for small lists due to the overhead of the divide-and-conquer approach. ‹#› ‹#›

33. Summary What we’ve learned so far Merge sort is a classic divide-and-conquer algorithm used for sorting a list or an array of elements. It operates by recursively dividing the input list into smaller halves until each sub list consists of only one element, which is inherently sorted. Then, it merges these smaller sorted lists, combining them in a way that ensures the merged list is sorted. The key operation in merge sort is the merging step, where two sorted arrays or sub lists are combined to create a single, sorted list. This merging process leverages the fact that both input sub lists are already sorted, allowing for a straightforward comparison and merging into a new sorted list. Merge sort is known for its stable sorting (maintaining the relative order of equal elements) and consistent performance, especially in scenarios where large amounts of data need to be sorted efficiently.

34. Thank you Respected Teachers & Fellow Classmates Special Guidance by: Nibedita Ma’am ‹#›