This chapter provides knowledge of merge sort. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Merge Sort 3/25/14 15:46 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Merge Sort 7 2 ⏐ 9 4 → 2 4 7 9 7 ⏐ 2 → 2 7 7→7 © 2014 Goodrich, Tamassia, Goldwasser 9 ⏐ 4 → 4 9 2→2 9→9 4→4 Merge Sort 1 Divide-and-Conquer ! Divide-and conquer is a ! Merge-sort is a sorting general algorithm design paradigm: n n n Divide: divide the input data S in two disjoint subsets S1 and S2 Recur: solve the subproblems associated with S1 and S2 Conquer: combine the solutions for S1 and S2 into a solution for S ! The base case for the recursion are subproblems of size 0 or 1 © 2014 Goodrich, Tamassia, Goldwasser Merge Sort ! algorithm based on the divide-and-conquer paradigm Like heap-sort n It has O(n log n) running time ! Unlike heap-sort n n It does not use an auxiliary priority queue It accesses data in a sequential manner (suitable to sort data on a disk) 2 1 Merge Sort 3/25/14 15:46 Merge-Sort ! Merge-sort on an input sequence S with n elements consists of three steps: n n n Divide: partition S into two sequences S1 and S2 of about n/2 elements each Recur: recursively sort S1 and S2 Conquer: merge S1 and S2 into a unique sorted sequence © 2014 Goodrich, Tamassia, Goldwasser Algorithm mergeSort(S) Input sequence S with n elements Output sequence S sorted according to C if () > 1 (S1, S2) ← partition(S, n/2) mergeSort(S1) mergeSort(S2) S ← merge(S1, S2) Merge Sort 3 Merging Two Sorted Sequences ! The conquer step of ! merge-sort consists of merging two sorted sequences A and B into a sorted sequence S containing the union of the elements of A and B Merging two sorted sequences, each with n/2 elements and implemented by means of a doubly linked list, takes O(n) time © 2014 Goodrich, Tamassia, Goldwasser Algorithm merge(A, B) Input sequences A and B with n/2 elements each Output sorted sequence of A ∪ B S ←
