Merge sort : In merge sort we will divide the array from middle recursively until we have only one element in sub-array. After that we will merge sub-array in ascending order. Time complexity for merge sort will be O(nlogn) as we are splitting the array from middle so each time it's getting half so for that it will be log(n) and while merging we are traversing the whole array so for that it will be O(n). So after combining both time complexity will be O(n)+O(logn)= O(nlogn) space complexity will be O(n) as we need a extra same size array to hold the unsorted array. class MergeSort { public static void sort ( int [] array) { int [] aux = new int [array. length ] ; sort (array , aux , 0 , array. length - 1 ) ; } private static void sort ( int [] array , int [] aux , int lo , int hi) { if (hi <= lo) return; int mid = (lo + hi) / 2 ; sort (arra...
Comments
Post a Comment