Merge Sort (Divide & Conquer)
Learn Merge Sort (Divide & Conquer) (Divide & Conquer, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Merge Sort as Divide and Conquer Divide and conquer solves a problem in three steps: divide it into smaller subproblems, conquer each one recursively, then combine the answers. Merge sort puts almost all the work in the combine step: split the array in half, sort both halves, then merge two sorted halves in O(n). That gives T(n) = 2T(n/2) + n , which is O(n log n) .