Merj sort

of 29

Please download to get full document.

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
16 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
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks