Merge Sort and Quick Sort in Java

[Harshsaini001]

1. Merge Sort:
   Merge Sort is a divide-and-conquer algorithm that recursively divides the array into two halves, sorts each half, and then merges them back together in sorted order.

How it works:
The array is recursively split in half until each subarray has one element (base case).
Then, during the merge step, the two halves are combined back together in sorted order by comparing elements from each half.
This continues until the entire array is merged and sorted.

Time Complexity: O(n log n) in all cases (best, average, and worst-case).
Space Complexity: O(n), because of the auxiliary array used for merging.

Key Characteristics:
Stable sorting algorithm (preserves the relative order of equal elements).
Performs well on large datasets, but uses extra space for the merging process.

2. Quick Sort:
   Quick Sort is another divide-and-conquer algorithm that selects a "pivot" element and partitions the array around the pivot so that elements less than the pivot come before it and elements greater than the pivot come after it. It then recursively sorts the two partitions.

How it works:
A pivot is chosen (commonly the last element or a random one).
The array is partitioned into two subarrays: one with elements smaller than the pivot and one with elements larger than the pivot.
The same process is applied recursively to both subarrays until the array is sorted.
Time Complexity:
Best and average case: O(n log n).
Worst case: O(n²) (if the pivot selection is poor, e.g., always the smallest or largest element).
Space Complexity: O(log n) due to the recursion stack, but no extra array is needed like in Merge Sort.

Key Characteristics:
In-place sorting algorithm (requires no extra space).
Not stable (does not preserve the relative order of equal elements).

[Harshsaini001]

Hii @strivedi4u , I want to write the solution of two main sorting algorithms in Java. Please assign me this issue under Hacktoberfest 2024.

[Harshcreator]

please assign me this issue under Hacktoberfest 2024

[KartikG2]

hello sir ,please assign this issue to me under Hacktoberfest'24

[N-nishita]

Hello SIr, I am a java developer ,please assign this issue for hactoberfest 2024 .