Sponsored
Sponsored
Merge Sort is a classic divide-and-conquer sorting algorithm that works in O(nlog(n)) time complexity and requires extra space proportional to the length of the array. The core concept is to divide the array into two halves, recursively sort each half, and then merge the sorted halves to produce a sorted array.
Time Complexity: O(nlog(n))
Space Complexity: O(n) (for temporary arrays used during merging)
1import java.util.Arrays;
2
3public class MergeSort {
4 public static void merge(int[] arr, int left, int mid, int right) {
5 int n1 = mid - left + 1;
6 int n2 = right - mid;
7 int[] L = new int[n1];
8 int[] R = new int[n2];
9 for (int i = 0; i < n1; i++)
10 L[i] = arr[left + i];
11 for (int j = 0; j < n2; j++)
12 R[j] = arr[mid + 1 + j];
13 int i = 0, j = 0, k = left;
14 while (i < n1 && j < n2) {
15 if (L[i] <= R[j]) {
16 arr[k] = L[i];
17 i++;
18 } else {
19 arr[k] = R[j];
20 j++;
21 }
22 k++;
23 }
24 while (i < n1) {
25 arr[k] = L[i];
26 i++;
27 k++;
28 }
29 while (j < n2) {
30 arr[k] = R[j];
31 j++;
32 k++;
33 }
34 }
35
36 public static void mergeSort(int[] arr, int left, int right) {
37 if (left < right) {
38 int mid = (left + right) / 2;
39 mergeSort(arr, left, mid);
40 mergeSort(arr, mid + 1, right);
41 merge(arr, left, mid, right);
42 }
43 }
44
45 public static void main(String[] args) {
46 int[] nums = {5, 2, 3, 1};
47 mergeSort(nums, 0, nums.length - 1);
48 System.out.println(Arrays.toString(nums));
49 }
50}Using Java, merge sort is implemented similarly; arrays L and R are created during the merge function. The method mergeSort recursively divides the array and then calls merge to sort and combine the divided arrays.
Quick Sort is an efficient, in-place sorting algorithm that works in average O(nlog(n)) time complexity. This approach involves selecting a 'pivot' element from the array and partitioning the remaining elements into two subarrays according to whether they are less than or greater than the pivot. The subarrays are then sorted recursively.
Time Complexity: O(n2) in the worst case, O(nlog(n)) on average.
Space Complexity: O(log(n)) for recursive stack space.
1
The C solution for quick sort uses Hoare's partition scheme, where we move indices inward until elements that should be swapped are found. The quickSort function recursively applies this process.