Previous:

September 19, 2023

example java arrays interviewingSorting an array is a Leetcode problem that presents this question:

Given an array of integers

`nums`

, sort the array in ascending order and return it.

You must solve the problem

without using any built-in functionsin`O(nlog(n))`

time complexity

You can do this using an algorithm called merge sort.

Merge sort is one of the most famous recursive algorithms, and it sorts an array by recursively halving it into smaller and smaller subarrays, until the subarrays only have a single element in them. A single-element subarray is technically already sorted. It then merges the subarrays back together by selecting the smallest elements from each subarray in order, so that the result is sorted.

```
void mergeSort(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
// Recursive helper function that sorts the specified subarray.
// Note: startIndex and endIndex are inclusive boundaries.
void mergeSort(int[] array, int startIndex, int endIndex) {
// If the subarray is less than two elements, we're done.
if(startIndex >= endIndex) {
return;
}
// Split the subarray into two sub-subarrays and mergesort them.
int centerIndex = (startIndex + endIndex) / 2;
mergeSort(array, startIndex, centerIndex);
mergeSort(array, centerIndex + 1, endIndex);
// Merge the two sorted sub-subarrays into a single subarray.
merge(array, startIndex, centerIndex, endIndex);
}
// Merge two sorted halves of a subarray into a single sorted subarray.
// Note: startIndex and endIndex are inclusive boundaries.
void merge(int[] array, int startIndex, int centerIndex, int endIndex) {
// Create copies of the left and right halves.
// Arrays.copyOfRange endIndex is exclusive, so add one.
int[] leftArray = Arrays.copyOfRange(array, startIndex, centerIndex + 1);
int[] rightArray = Arrays.copyOfRange(array, centerIndex + 1, endIndex + 1);
int arrayIndex = startIndex;
int leftIndex = 0;
int rightIndex = 0;
// Look through the left and right halves, selecting the smallest from each in order.
while(leftIndex < leftArray.length && rightIndex < rightArray.length) {
if(leftArray[leftIndex] < rightArray[rightIndex]) {
array[arrayIndex] = leftArray[leftIndex];
leftIndex++;
} else {
array[arrayIndex] = rightArray[rightIndex];
rightIndex++;
}
arrayIndex++;
}
// Copy the remaining values from the left array into the output.
while(leftIndex < leftArray.length) {
array[arrayIndex] = leftArray[leftIndex];
leftIndex++;
arrayIndex++;
}
// Copy the remaining values from the right array into the output.
while(rightIndex < rightArray.length) {
array[arrayIndex] = rightArray[rightIndex];
rightIndex++;
arrayIndex++;
}
}
```

The algorithmic complexity of recursive algorithms depend on exactly how you’re splitting up your data.

For merge sort, the algorithmic complexity is `O(n log n)`

. Here’s an image that demonstrates why:

Each “level” of the merge sort algorithm requires `O(n)`

complexity, because it merges the sorted subarrays together. And since it splits the data in half each level, the number of levels will be `log`

. So the total steps is _{2}n`n * log`

._{2}n

Similar to how you drop multipliers when converting from individual steps to big O notation, `n * log`

becomes _{2}n`O(n * log n)`

.

That’s the algorithmic complexity for merge sort, but the algorithmic complexity of other recursive algorithms depends on what they’re doing. For example, the recursive `factorial()`

function above has an algorithmic complexity of `O(n)`

. I’ll talk more about recursive algorithmic complexity in the next tutorial.

Previous:

I posted a new code along for the merge sort algorithm.

Check it out here:

Use recursion to sort an array.

Happy Coding is a community of folks just like you learning about coding.

Do you have a comment or question? Post it here!

Comments are powered by the Happy Coding forum. This page has a corresponding forum post, and replies to that post show up as comments here. Click the button above to go to the forum to post a comment!