Sorting and Selection

Sorting and Selection

1. Merge-Sort

   • Divide-and-Conquer
     • Divide (divide the input data into 2 or more disjoint subsets), conquer (recursively solve the subproblems), combine (merge the sorted sequences)
       • Input sequences processed
       • Output sequences generated
   • Array-Based Implementation
     • Implementation of recursive algorithm for Java array
   • Running time
     • Each node represents the time spent in a particular recursive call
     • O(n log n)
   • Alternative Implementations
     • Sorting Linked Lists
     • A Bottom-Up (Nonrecursive) Merge-Sort

Bilder und Dateien der Mindmap