Merge Sort
Generate Random Values
Enter the number of random values to generate
Input Your Own Values
Enter a list of numbers separated by a comma
Whats goin on?
Merge sort is an algorithm that utilizes recursion. The function splits the array into halves and calls itself on each half. It then merges the the result of those functions and returns a combined sorted array. Because the algorithm first divides the input array, each subsequent call occurs on only half of the original. This process repeats until the algorithm is being called on an array with only a single element at which point, the function calls to begin to resolve. The previous function call receives the resolved single value arrays and merges them in order of the desired sorting pattern. The function then returns this sorted array and the previous function call repeats the process until the entire array has been rebuilt sorted.
Performance
Time complexity
Because each recursive call operates on only half the array, the size of the array decreases logarithmically. Rebuilding the array occurs in a single iteration through both arrays. This means that the time complexity of this algorithm is
O(nlog(n))
Space complexity
Merge sort combines two halves of an array into another array. This means that the space complexity of this algorithm is
O(n)