Sorting Algorithms

Common Sorting Algorithms

• Bubble Sort (comparison-based, O(n²))
• Merge Sort (divide-and-conquer, O(n log n))
• Quick Sort (divide-and-conquer, O(n log n) average)
• Counting Sort (non-comparison-based, O(n + k))
• Heap Sort (comparison-based, O(n log n))
• Insertion Sort (comparison-based, O(n²))
• Selection Sort (comparison-based, O(n²))

Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm. It works by recursively splitting the array in half, sorting each half, and then merging the sorted halves back together.

Algorithm:

1. Divide the unsorted array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into a single sorted array.

Time Complexity:

• O(n log n) (for all cases: best, average, and worst).

Quick Sort

Quick Sort is a popular, efficient sorting algorithm that works by selecting a pivot element and partitioning the array into elements smaller than the pivot and larger than the pivot. It then recursively sorts the subarrays.

Algorithm:

1. Pick a pivot element (typically the first, last, or a random element).
2. Partition the array into two parts:
   • Elements smaller than the pivot go to the left.
   • Elements larger than the pivot go to the right.
3. Recursively apply the same process to the left and right subarrays.
4. Combine the results into the sorted array.

Time Complexity:

• Best and Average Case: O(n log n)
• Worst Case (rare): O(n²)

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm. It works by counting the occurrences of each unique element and using this information to place elements into the correct position in the sorted array. It is efficient when the range of values is not significantly larger than the number of elements.

Algorithm:

1. Find the range of the elements (maximum and minimum values).
2. Create a count array of this range, and initialize it to zero.
3. Count the occurrences of each element and store them in the count array.
4. Modify the count array by adding the count of the previous elements (cumulative sum).
5. Place the elements into the sorted array based on the cumulative counts.

Time Complexity:

• O(n + k) (where n is the number of elements, and k is the range of the input).

---

Other Sorting Algorithms (Briefly Mentioned)

• Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order. Time complexity: O(n²).
• Heap Sort: Uses a heap data structure to sort the array. Time complexity: O(n log n).
• Insertion Sort: Builds the sorted array one element at a time. Time complexity: O(n²).
• Selection Sort: Selects the smallest element from the unsorted part and swaps it with the first unsorted element. Time complexity: O(n²).

---

Tasks

1. Time Complexity Analysis: Take some time to explore and understand the time complexities of the sorting algorithms mentioned. Try to reason out why each algorithm has its specific complexity.

2. Implementation: Implement your own versions of Merge Sort and Quick Sort based solely on the algorithm steps provided. Avoid looking at existing code initially to enhance your understanding. Once you have completed the implementations, upload your code to the repository link you shared in the Google Doc.