Top Coding Algorithm — Sorting

Merge Sort, Bubble Sort, and Quick Sort

In this post, we will go through some common sorting algorithms and implement them in python (code).

Merge Sort

Merge sort follows:

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

There are basically 2 subproblems in merge sort,

1. Divide the array into 2 halves
2. Merge 2 sorted array

Question 1 is simple, let’s try to solve question 2. How to merge 2 sorted array into 1 sorted array?

Suppose we have 2 sorted array:
  a = [2, 13, 32]
  b = [1, 5, 11, 22]
Design an algorithm to merge them into 1 sorted array.

The problem is solved by using 3 pointers. i, j, k are pointers for left array, right array and result array.