Python Program - Merge Sort

Merge sort is a divide and conquer algorithm. It is based on the idea of dividing the unsorted array into several sub-array until each sub-array consists of a single element and merging those sub-array in such a way that results into a sorted array. The process step of merge sort can be summarized as follows:

• Divide: Divide the unsorted array into several sub-array until each sub-array contains only single element.
• Merge: Merge the sub-arrays in such way that results into sorted array and merge until achieves the original array.
• Merging technique: the first element of the two sub-arrays is considered and compared. For ascending order sorting, the element with smaller value is taken from the sub-array and becomes a new element of the sorted array. This process is repeated until both sub-array are emptied and the merged array becomes sorted array.

Example:

To understand the merge sort, lets consider an unsorted array [4, 9, -4] (right side array created after 11th process in the below diagram) and discuss each step taken to sort the array in ascending order.

At the first step, the array [4, 9, -4] is divided into two sub-array. The first sub-array contains [4, 9] and second sub-array contains [-4]. As the number of element in the first sub-array is greater than one, it is further divided into sub-arrays consisting of elements [4] and [9] respectively. As the number of elements in all sub-arrays is one, hence the further dividing of the array can not be done.

In the merging process, The sub-arrays formed in the last step are combined together using the process mentioned above to form a sorted array. First, [4] and [9] sub-arrays are merged together to form a sorted sub-array [4, 9]. Then [4, 9] and [-4] sub-arrays are merged together to form final sorted array [-4, 4, 9]

Implementation of Merge Sort

public class MyClass {
  // function for merge sort - splits the array 
  // and call merge function to sort and merge the array
  // mergesort is a recursive function
  static void mergesort(int Array[], int left, int right) {
    if (left < right) { 
      int mid = left + (right - left)/2;
      mergesort(Array, left, mid);
      mergesort(Array, mid+1, right);
      merge(Array, left, mid, right);
    }
  }

  // merge function performs sort and merge operations
  // for mergesort function
  static void merge(int Array[], int left, int mid, int right) {
    // Create two temporary array to hold split 
    // elements of main array 
    int n1 = mid - left + 1; //no of elements in LeftArray
    int n2 = right - mid;     //no of elements in RightArray    
    int LeftArray[] = new int[n1];
    int[] RightArray = new int [n2];

    for(int i=0; i < n1; i++) { 
      LeftArray[i] = Array[left + i];
    }
    
    for(int i=0; i < n2; i++) { 
      RightArray[i] = Array[mid + i + 1];
    }

    // In below section x, y and z represents index number
    // of LeftArray, RightArray and Array respectively
    int x=0, y=0, z=left;
    while(x < n1 && y < n2) {
      if(LeftArray[x] < RightArray[y]) { 
        Array[z] = LeftArray[x]; 
        x++; 
      }
      else { 
       Array[z] = RightArray[y];  
       y++; 
      }
      z++;
    }

    // Copying the remaining elements of LeftArray
    while(x < n1) { 
       Array[z] = LeftArray[x];  
       x++;  
       z++;
    }

    // Copying the remaining elements of RightArray
    while(y < n2) { 
      Array[z] = RightArray[y]; 
      y++;  
      z++; 
    }
  }

  // function to print array
  static void PrintArray(int Array[]) { 
    int n = Array.length; 
    for (int i=0; i<n; i++) 
      System.out.print(Array[i] + " "); 
    System.out.println(); 
  } 

  // test the code
  public static void main(String[] args) {
    int[] MyArray = {10, 1, 23, 50, 4, 9, -4};
    int n = MyArray.length;
    System.out.println("Original Array");
    PrintArray(MyArray);

    mergesort(MyArray, 0, n-1);
    System.out.println("\nSorted Array");
    PrintArray(MyArray); 
  }
}

The above code will give the following output:

Original Array
10 1 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 

Time Complexity:

In all cases (worst, average and best), merge sort always divides the array until all sub-arrays contains single element and takes linear time to merge those sub-arrays. Dividing process has time complexity Θ(logN) and merging process has time complexity Θ(N). Therefore, in all cases, the time complexity of merge sort is Θ(NlogN).