In computer science, there are different kinds of sorting algorithms to sort data in some order. These algorithms have different levels of performances and they are also implemented in ordering different kinds of data. In this article, quick sort and merge sort are discussed and implemented in JavaScript.
Merge Sort
Merge sort is one of the efficient algorithms used to sort data in ascending or depending order. In this algorithm, a given array is divided into its elements, and these elements are compared and arranged in the right order, merged together in either ascending or defending order.
In implementing merge sort algorithm, a helper function is defined that receives two arrays and returns an array of composed of the elements of the two input arrays sorted in order as shown below. To achieve the order, three while loops are implemented. The first while loop compares each element of the first array with the elements of the second array. The result of these comparisons is pushed to the output array saved as merged. The other two while loops take care of the cases where some of the elements of one array are greater or less than the other. In such cases, the rest of the elements are pushed to merged.
Once the helper function is defined, it is invoked inside the main sort function that runs recursively. In the mergeSort function as shown below, the input array is divided into half components -left and right. When this function is invoked, it checks if the size of the input array is 1 or 0 and returns the array if it is true. If the input array size is larger than 1, it calculates the mid point index of the input array. Then the left portion of the input array is recursively divided the resulting array until its size is 1 or 0. When it does, merge helper function is invoked recursively until an array is returned to the left variable. Then the right variable is run recursively until an array of ordered elements are returned.
Performance of Merge Sort
As the input array is being divided into half every recursive call of mergeSort, the recursive processing of division takes O(log n). However, the merge helper function has to sort and merge the two input arrays for every recursive call of mergeSort. The merging of these arrays takes O(n). Consequently, merge sort algorithm depends on the input size as O(n log n). On the other hand, the above implementation of merge sort has space complexity of O(n) due to the different variables defined inside the two functions. In the helper function, merged is takes an array which is O(n) while the two variables take constant space O(1). Consequently, the helper function has space complexity of O(n).
Quick Sort
Quick sort is one of the efficient algorithms that are implemented in sorting data in ascending or descending order. In this algorithm, a given array is divided into based on a section of an element from the array. An element is chosen from the given array and the the array elements are then divided into elements that are less than the element on one side and the other elements onto the other side of the element. In so doing, the right index of the chosen element is determined. This is then recursively applied to the rest of the elements of the array until all the elements take their right position.
In implementing this algorithm, two helper functions were used. The first function shown below is accepts an array, starting index, and end index. In this implementation, the first element of the array is chosen to find its right index in the input array. Then the rest of the elements of the array are compared with the first element. If an element is less than the chosen element, the variable pivotIndex is incremented and the element is swapped with the previous element. When the loop ends, the pivotIndex is the right index of the chosen element. Then, the pivot element is swapped to its rightful position in the array.
Once these two helper functions are defined, the recursive quick sort function can be implemented. In the main sorting function, the second and third input arguments are compared. As long as this comparison is satisfied, quickSort function is recursively invoked to portions of the slices of input array as shown below. Each recursive call of quickSort results sorts the input array by obtaining the right index of a pivot element.
Performance of Quick Sort
Unlike merge sort, quick sort algorithm time complexity performance depends how the pivot point is chosen and the type of input entered. The best case scenario for quick sort is O(nlogn) if the input is not sorted when it is implemented. For a sorted input if the pivot is selected to be the first element of the array, the decomposition of the array into two will be uneven as more elements will be on one side than the other. Consequently, the time complexity will be O(n^2) than O(nlogn). Therefore, it is recommended that a random element from the array should be selected as pivot.
Top comments (0)