Merge sort is the algorithm which follows divide and conquer approach.
How Merge Sort works:
- Merge Sort works by breaking the Array (or Linked List) into 2 equal parts say Left half and Right half.
- Again break 2 Array (or Linked List) that we got in Step 1 in two equal parts each.
- Repeat above steps until only 1 element remains in Array (or Linked List) because list with only 1 element is always sorted.
- So in each step we are breaking the list in Left half and Right half.
- When complete list is divided and contains only Single element in Left and Right half each,Start comparing and sorting each Left and Right half, So that portion of Array (or Linked List) will be sorted.
- Repeat Step 5 for all the remaining Left and Right half and complete Array (or Linked List) will be sorted.
public class MergeSort {
public static void main(String args[]) {
int arr[] = { 90, 23, 101, 45, 65, 23, 67, 89, 34, 23 };
System.out.println("Input array :: ");
printArray(arr);
trivialMergeSort(arr, 0, arr.length);
System.out.println("Sorted array :: ");
printArray(arr);
}
static void printArray(int arr[]) {
for (int i : arr)
System.out.print(i + " ");
System.out.println();
}
public static void trivialMergeSort(int arr[], int fromIndex, int toIndex) {
// If array is of size 1 or 0, nothing to sort.
if (arr.length < 2) {
return;
}
int[] leftArray = new int[arr.length / 2];
int[] rightArray = new int[arr.length - leftArray.length];
for (int i = 0, j = fromIndex; i < leftArray.length; i++, j++) {
leftArray[i] = arr[j];
}
for (int i = 0, j = leftArray.length; i < rightArray.length; i++, j++) {
rightArray[i] = arr[j];
}
//Recursive Call
trivialMergeSort(leftArray, fromIndex, leftArray.length);
trivialMergeSort(rightArray, fromIndex, rightArray.length);
int left = 0;
int right = 0;
int targetIndex = fromIndex;
// Merge the Left and Right Arrays
while (left < leftArray.length && right < rightArray.length) {
arr[targetIndex++] = rightArray[right] < leftArray[left] ? rightArray[right++] : leftArray[left++];
}
// Copy remaining elements of leftArray[] if any
while (left < leftArray.length) {
arr[targetIndex++] = leftArray[left++];
}
// Copy remaining elements of rightArray[] if any
while (right < rightArray.length) {
arr[targetIndex++] = rightArray[right++];
}
}
}
Output:
Input array ::
90 23 101 45 65 23 67 89 34 23
Sorted array ::
23 23 23 34 45 65 67 89 90 101
Complexity:
| Complexity | Best case | Average Case | Worst Case |
|---|---|---|---|
| Time Complexity | O(n log n) | O(n log n) | O(n log n) |
| Space Complexity | O(n) |
Harshit Jain 