Quick look into Divide and Conquer algos : Merge and Quick sort

What is Divide and Conquer strategy in algorithms?

Divide and Conquer is a technique in which a larger problem is broken down into smaller sub problems first. The sub problems are then solved and the results of those sub problems are combined to give us the final answer. Read more about it here.

In both merge and quick sort, the items we sort, let’s say an array of elements are first divided into sub arrays. Sorting is done on those sub arrays recursively and then are combined to finally get a sorted array.

Let’s dive deeper into each.

1. Merge sort

Algorithm for merge sort:

1. Divide the array into two halves : arr / 2. Divide the resulting sub arrays in the same manner. Divide until we are left with single element remains in each array.
2. Now repeatedly merge these sub arrays until we are left with one single array. While merging two arrays we compare the elements of the sub arrays to arrange them in sorted order.

Merge sort

Python implementation of Merge sort:

def merge_arr(arr1, arr2):
  i, j = 0, 0 # pointers to track element in both array
  sorted_merged_arr = [] # array to store the resultant array
  
  while i < len(arr1) and j < len(arr2):
    # push the smaller element in the resultant array
    if arr1[i] < arr2[j]:
      sorted_merged_arr.append(arr1[i])
      i += 1 
    else:
      sorted_merged_arr.append(arr2[j])
      j += 1
      
  # check if any value remained in arr1
  while i < len(arr1):
    sorted_merged_arr.append(arr1[i])
    i += 1
        
  # check if any value remained in arr2
  while j < len(arr2):
    sorted_merged_arr.append(arr2[j])
    j += 1

  return sorted_merged_arr

def merge_sort(arr):
  # if arr contains single element return it, as it is already sorted
  if len(arr) == 1:
    return arr
  
  mid = len(arr) // 2 # find the mid element
  # divide into two halves
  left = arr[:mid]
  right = arr[mid:]
  
  # recursively call merge_sort on both the halves now
  arr1 = merge_sort(left)
  arr2 = merge_sort(right)
  
  sorted_arr = merge_arr(arr1, arr2)
  return sorted_arr
  
arr = [5, 7, 3, 1, 9, 4]
print(merge_sort(arr)) # OUTPUT : [1, 3, 4, 5, 7, 9]

2. Quick sort

Algorithm for quick sort

1. Select a ‘pivot’ element from the array. Now, partition the remaining elements into 2 sub arrays depending on whether they are less than or greater than the pivot element.
2. Recursively apply the quick sort algorithm to both the sub arrays.

One additional thing we need to know for quick sort is how to perform partition :

1. Selecting a pivot element : choosing the first element, the last element or a random element.
2. Iterate over the array, maintain two pointer, i and j, i points to the part of the array with elements smaller than that of pivot element and j points to the current element.
   For each element at ‘j’ if it is smaller than or equal to pivot element then increment i by 1 and swap i and j index elements.
3. After that swap element at (i+1) and the pivot.
4. Return the index (i+1) as pivot index. This index represents the position where the pivot is now placed after the partitioning.

Example of partition

Python implementation of Quick sort:

def partition(arr, low, high):
  # choose a pivot element
  # a pivot element can be any element
  # here we are choosing the right most element
  pivot = arr[high]
  
  # we will use pointer 'i' to point to the 
  # array with elements that are smaller than pivot element
  i = low - 1
  
  # iterate over the array
  for j in range(low, high):
    if arr[j] <= pivot:
      i += 1
      # swap arr[i] and arr[j]
      arr[i], arr[j] = arr[j], arr[i]
      
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1
  
  
def quick_sort(arr, low, high):
  if low < high:
    pivot = partition(arr, low, high)
    
    # call quicksort recursively on both sub arrays
    quick_sort(arr, low, pivot - 1)
    quick_sort(arr, pivot + 1, high)
    
    
  
arr = [5, 7, 3, 1, 9, 4]
high = len(arr) - 1
quick_sort(arr, 0, high)
print(arr) # OUTPUT : [1, 3, 4, 5, 7, 9]

Time and Space Complexity of both Merge and Quick sort

+------------+------------------------------+------------------+
| Algorithms |       Time complexity        | Space complexity |
+------------+------------------------------+------------------+
| Merge sort | O(nlogn) (all cases)         | O(n)             |
| Quick sort | O(nlogn) (best and avg case) | O(1)             |
|            | O(n^2) (worst case)          |                  |
+------------+------------------------------+------------------+