# Merj sort

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
29 pages
0 downs
32 views
Share
Description
1. TOPIC :- MERGE SORT 2. BASIC CONCEPT OF MERGE SORT I. Uses divide and conquer technique. II. array is divided into sub-array. III. Sub-arrays merged to get sorted…
Transcript
• 1. TOPIC :- MERGE SORT
• 2. BASIC CONCEPT OF MERGE SORT I. Uses divide and conquer technique. II. array is divided into sub-array. III. Sub-arrays merged to get sorted result.
• 3. DIVIDE AND CONQUER Divide and conquer method for algorithm design: • Divide: Large problem is divided into sub-problems • Conquer: recursively solve the sub-problems • Combine: • Take the solutions to the sub-problems • “merge” these solutions into final solution 3
• 4. DRY RUN OF PROGRAM 4
• 5. CONTD. 5
• 6. CONTD. 6
• 7. CONTD. 7
• 8. CONTD. 8
• 9. CONTD. 9
• 10. CONTD. 10
• 11. CONTD. 11
• 12. CONTD. 12
• 13. CONTD. 13
• 14. CONTD. 14
• 15. CONTD. 15
• 16. CONTD. 16
• 17. CONTD. 17
• 18. CONTD. 18
• 19. CONTD. 19
• 20. CONTD. 20
• 21. CONTD. 21
• 22. CONTD. 22
• 23. CONTD. 23
• 24. CONTD. 24
• 25. AT THE END SORTED 25
• 26. MERGING FUNCTION void merge ( int , int , int ) ; void merge _ sort(int low , int high) { int mid; if(low<high) { mid=( low + high)/2 ; merge _ sort ( low , mid) ; merge _ sort(mid+1,high); merge ( low , mid , high) ; } }
• 27. IMPLEMENTATION
• 28. SUMMARY OF SORTING ALGORITHMS Algorithm Time Notes selection-sort O(n2) in-place slow (good for small inputs) insertion-sort O(n2) in-place slow (good for small inputs) quick-sort O(n log n) expected in-place, randomized fastest (good for large inputs) merge-sort O (n log n) sequential data access fast (good for huge inputs)
• 29. ANY QUESTION…
• Related Search
Similar documents

View more...