Provide a simple code sample of Merge sort in Java. Please and thank you
Provide a simple code sample of Merge sort in Java.
Please and thank you
Merge Sort Algorithm
MergeSort(arr[], left, right):
If left < right:
1. Find the middle point to divide the array into two halves:
middle = (left + right) / 2
2. Call MergeSort for the left half:
MergeSort(arr, left, middle)
3. Call MergeSort for the right half:
MergeSort(arr, middle + 1, right)
4. Merge the two halves:
Merge(arr, left, middle, right)
Merge(arr[], left, middle, right):
1. Find the sizes of the two subarrays to be merged:
n1 = middle - left + 1
n2 = right - middle
2. Create temporary arrays leftArr[0...n1] and rightArr[0...n2]
3. Copy data to the temporary arrays leftArr[] and rightArr[]:
for i = 0 to n1 - 1:
leftArr[i] = arr[left + i]
for j = 0 to n2 - 1:
rightArr[j] = arr[middle + 1 + j]
4. Merge the temporary arrays back into the original array arr[left...right]:
i = 0
j = 0
k = left
while i < n1 and j < n2:
if leftArr[i] <= rightArr[j]:
arr[k] = leftArr[i]
i++
else:
arr[k] = rightArr[j]
j++
k++
5. Copy the remaining elements of leftArr[], if any:
while i < n1:
arr[k] = leftArr[i]
i++
k++
6. Copy the remaining elements of rightArr[], if any:
while j < n2:
arr[k] = rightArr[j]
j++
k++
Step by step
Solved in 4 steps with 2 images
