We have see the brute force approach already. How can we speed things up? Think of the outer loop from iterating through the array to only the height of the tree.
Question ()
Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.
Why this thing is not in-place? The merge process has to be implemented with an extra array.
the base case - only one element we just return it
divide each array into two subarrays (what if the number is odd? does mid+1 handle it?)
we conquer left and right subarray by calling mergeSort on it
we use a merge function to combine the sorted results. merge two sorted arrays remember?
Code w/ temp array
public void sortArray(int[] A) {
if (A == null || A.length == 0)
return;
// we want to create the temp here instead of in mergeSort
// cause then we have to do it everytime we call merge sort
int[] temp = new int[A.length];
mergeSort(A, temp, 0, A.length - 1);
}
private void mergeSort(int[] A, int[] temp, int start, int end) {
// base case
// only one element, just return it
if (start == end) {
return;
}
// divide
// we want to divide the array into two havles
// the left half is A[start...mid]] the right half is A[mid+1...end]
int midpoint = (start + end) / 2;
// conquer
mergeSort(A, temp, start, midpoint);
mergeSort(A, temp, midpoint + 1, end);
// combine
merge(A, temp, start, midpoint, end);
}
private void merge(int[] A, int[] temp, int start, int midpoint, int end) {
int leftPointer = start;
int rightPointer = midpoint + 1;
// merge until the shorter one is finished
int i = leftPointer;
while (leftPointer <= midpoint && rightPointer <= end) {
if (A[leftPointer] < A[rightPointer]) {
temp[i++] = A[leftPointer++];
} else {
temp[i++] = A[rightPointer++];
}
}
// if left array has leftovers
while (leftPointer <= midpoint) {
temp[i++] = A[leftPointer++];
}
// else if the right array has leftovers
while (rightPointer <= end) {
temp[i++] = A[rightPointer++];
}
// at the end, we have to put the temp info back to the actual array
for (int a = start; a <= end; a++) {
A[a] = temp[a];
}
}
Code w/ new slice
Programs with side effects, such as modifying a shared temp array, cannot be easily parallelized because mutual exclusion has to be involved.
def sortIntegers2(self, A: List[int]) -> None:
n = len(A)
if n == 0:
return
sorted_list = merge_sort(A, 0, n-1)
for i in range(n):
A[i] = sorted_list[i]
return
def merge_sort(A: List[int], start: int, end: int) -> List[int]:
# print(f'start: {start} end: {end} slide: {A[start:end+1]}')
# base
if start == end:
return [A[start]]
# divide
mid = (start + end) // 2
# conquer
left_arr = merge_sort(A, start, mid)
right_arr = merge_sort(A, mid+1, end)
# merge
merged = merge(left_arr, right_arr)
return merged
def merge(left_arr: List[int], right_arr: List[int]) -> List[int]:
result = []
i = 0
j = 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] <= right_arr[j]:
result.append(left_arr[i])
i += 1
else:
result.append(right_arr[j])
j += 1
if i < len(left_arr):
result.extend(left_arr[i:])
if j < len(right_arr):
result.extend(right_arr[j:])
return result
Concurrent Code
func sortIntegers2 (A *[]int) {
if A == nil || len(*A) <= 1 {
return
}
inputList := *A
n := len(inputList)
ch := make(chan []int)
go mergeSort(inputList, ch)
sortedList := <- ch
for i := 0; i < n; i++ {
inputList[i] = sortedList[i]
}
return
}
func mergeSort (list []int, ch chan []int) {
n := len(list)
if n == 1 {
ch <- list
return
}
// divide
mid := n / 2
leftCh := make(chan []int)
rightCh := make(chan []int)
// conquer
go mergeSort(list[:mid], leftCh)
go mergeSort(list[mid:], rightCh)
// merge
leftList := <- leftCh
rightList := <- rightCh
close(leftCh)
close(rightCh)
ch <- merge(leftList, rightList)
}
func merge (leftList []int, rightList []int) []int {
result := []int{}
i := 0
j := 0
for i < len(leftList) && j < len(rightList) {
if leftList[i] <= rightList[j] {
result = append(result, leftList[i])
i++
} else {
result = append(result, rightList[j])
j++
}
}
if i < len(leftList) {
result = append(result, leftList[i:]...)
}
if j < len(rightList) {
result = append(result, rightList[j:]...)
}
return result
}
Conclusion
The recurrence is T(n) = 2T(n/2) + n.
Merge sort is undoubtably fast with its O(nlogn) runtime. But it does require an extra O(n) space for its merging step. Next up, we will introduce another sorting algorithm with average O(nlogn) time and O(1) space. Stay tuned.
References
In practice, the concurrent code will not run faster by default. There is a cost (overhead to create a goroutine, go scheduler to schedule the goroutine, gc to terminate the goroutine, etc) associated with making the run concurrent. The break even point is around 1000 elements from this .
