Merge Sort

Merge Sort

Merge sort follows the divide and conquer paradigm.

For mergesort

1. We break the array into two subarrays to be sorted and then combine the ordered subarrays to make the whole ordered array;
2. We do the two recursive calls before working on the whole array;
3. The array is divided in half;

Pros

1. Mergesort guarantees to sort an array of N items in time proportional to N log N, no matter what the input.

Cons

1. Its prime disadvantage is that it uses extra space proportional to N.

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

Example

Example: Sorting [38, 27, 43, 3, 9, 82, 10]

Let’s walk through sorting the array [38, 27, 43, 3, 9, 82, 10] using merge sort.

1. Divide:
   1. Split array into [38, 27, 43] and [3, 9, 82, 10].
   2. Split [38, 27, 43] into [38] and [27, 43].
   3. Split [27, 43] into [27] and [43].
   4. Split [3, 9, 82, 10] into [3, 9] and [82, 10].
   5. Split [3, 9] into [3] and [9].
   6. Split [82, 10] into [82] and [10].

1. Conquer (Merge):
   1. Merge [27] and [43] → [27, 43].
   2. Merge [38] and [27, 43] → [27, 38, 43].
   3. Merge [3] and [9] → [3, 9].
   4. Merge [82] and [10] → [10, 82].
   5. Merge [3, 9] and [10, 82] → [3, 9, 10, 82].
   6. Merge [27, 38, 43] and [3, 9, 10, 82] → Compare and merge:
      1. L = [27, 38, 43], R = [3, 9, 10, 82]
      2. Compare 27 vs 3 → Pick 3
      3. Compare 27 vs 9 → Pick 9
      4. Compare 27 vs 10 → Pick 10
      5. Compare 27 vs 82 → Pick 27
      6. Compare 38 vs 82 → Pick 38
      7. Compare 43 vs 82 → Pick 43
      8. Take 82

1. Final array: [3, 9, 10, 27, 38, 43, 82]

Steps of the Merge Method

1. Input: The merge method takes two sorted subarrays (or arrays) as input. For example, if the original array is [4, 7, 2, 5], it might be divided into two sorted subarrays: [4, 7] and [2, 5].
2. Create a Temporary Array: A temporary array is created to store the merged result. This ensures the original array isn’t overwritten prematurely.
3. Compare and Merge:
   1. Two pointers (e.g., i and j) are used to track the current elements in the first and second subarrays, respectively.
   2. Compare the elements at i and j:
      1. If the element in the first subarray (arr[i]) is smaller or equal, copy it to the temporary array and increment i.
      2. Otherwise, copy the element from the second subarray (arr[j]) and increment j.
   3. Move the temporary array’s index forward after each copy.
   4. Continue until one subarray is exhausted.
4. Copy Remaining Elements:
   1. If any elements remain in the first subarray (i.e., i hasn’t reached the end), copy them to the temporary array.
   2. Similarly, copy any remaining elements from the second subarray.
5. Copy Back to Original Array: Transfer the sorted elements from the temporary array back to the original array in the appropriate range.

Complexity analysis

1. Time Complexity: O(n log n) for all cases.
2. Space Complexity: O(n) for temporary arrays during merging.
3. Stable: Maintains relative order of equal elements.
4. Use Case: Efficient for large datasets, especially linked lists, but requires extra space.