Problem Overview
A Divide & Conquer approach is fairly straightforward to concept understand.

1. Divide the problem instance into smaller subproblems.

2. Solve each subproblem (recursively).

3. Combine smaller solutions to solve the original instance.
Many applications of this concept exist in algorithms, today we will look at Merge Sort, Quick Sort & Binary Search Trees. We will also discover a new problem known as the Convex Hull which is a big problem in game development.
Merge Sort
The idea of Merge Sort is:
 Imagine we recursively divided an array (we wanted to sort) into halves, until we reach single element partitions.
 We then recursively merge the partitions, where we have a process that maintains sorting after partitions are merged.
 When we finally merge the last two partitions, we have a sorted array.
Lets take a look at some pseudocode:
ALGORITHM MergeSort (A[0 . . . n − 1]) /* Sort an array using a divideandconquer merge sort. */ /* INPUT : An array A[0 . . . n − 1] of orderable elements. */ /* OUTPUT : An array A[0 . . . n − 1] sorted in ascending order. */ 1: if n > 1 then 2: B = A[0...⌊n/2⌋−1]/*B is first half of A*/ 3: C = A[⌊n/2⌋...n−1]/*C is second half of A*/ 4: MergeSort (B) 5: MergeSort (C) 6: Merge (B,C,A) /* Merge B and C to help sort A */ 7: end if
Given two sorted subarrays B, C, want to merge them together to form a sorted A.
Idea:

1 Consider first element of each subarray, i.e, B[0] and C[0]. Compare them. Whichever one is smaller, copy to A[0], and increment current pointer of subarrays that has smaller element and A.

2 Repeat until one of subarray is empty. Then copy the rest of subarray to A.
Some things to note:
 Guarantees O(n log n) time complexity, regardless of the original distribution of data – this sorting method is insensitive to the data distribution.
 The main drawback in this method is the extra space required for merging two partitions/subarrays, e.g. B and C from pseudocode.
 Merge sort is a stable sorting method.
Quick Sort
 Quicksort is such a sorting algorithm, often the best practical choice in terms of efficiency because of its good performance on the average case.
 Merge sort has consistent behaviour for all inputs – what if we seek an algorithm that is fast for the average case?
 QuickSort is a divide and conquer algorithm.
Idea:

1. Select an element from the array for which, we hope, about half the elements will come before and a half after in a sorted array. Call this element the pivot.

2. Partition the array so that all elements with a value less than the pivot are in one subarray, and larger elements come in the other subarray.

3. Swap pivot into the position of an array that is between the partitions.

4. Recursively apply the same procedure on the two subarrays separately.

5. Terminate when only subarrays are of one element.

6. When terminate, because we do things in place, the resulting array is sorted.

Best Case:

Occurs when the pivot repeatedly splits the dataset into two equalsized subsets.

The complexity is O(nlog2n).


Worst Case:

If the pivot is chosen poorly, one of the partitions may be empty, and the other reduced by only one element.

Then the quicksort is slower than bruteforce sorting (due to partitioning overheads).

The complexity is n+(n−1)+(n−2)+...+1≈n2/2∈O(n2).

Occurs when the array is already sorted or reverse order sorted.


Average case:

The number of comparisons is≈1.39nlogn.

39% more comparisons than merge sort.

But faster than merge sort in practice because of the lower cost of other highfrequency operations, and uses considerably less space (no need to copy to temporary arrays).

Binary Search Trees