Sorting Algorithms: Bubble Sort and Merge Sort

Sorting Algorithms

Bubble Sort

• A simple sorting algorithm that works by repeatedly iterating through the data and swapping adjacent elements if they are in the wrong order.
• Time complexity: O(n^2) in worst and average cases, O(n) in best case.
• Space complexity: O(1) since it only uses a small amount of extra memory.
• Not suitable for large data sets due to its high time complexity.

Merge Sort

• A divide-and-conquer algorithm that divides the data into smaller chunks, sorts each chunk, and then merges the sorted chunks.
• Time complexity: O(n log n) in all cases.
• Space complexity: O(n) since it requires extra memory to store the temporary arrays.
• Stable sorting algorithm, meaning it maintains the relative order of equal elements.

Quick Sort

• A divide-and-conquer algorithm that selects a pivot element, partitions the data around the pivot, and then recursively sorts the sub-partitions.
• Time complexity: O(n log n) in average and best cases, O(n^2) in worst case.
• Space complexity: O(log n) in average and best cases, O(n) in worst case.
• Not stable, as it can swap equal elements.

Heap Sort

• A comparison-based sorting algorithm that uses a binary heap data structure to sort the data.
• Time complexity: O(n log n) in all cases.
• Space complexity: O(1) since it only uses a small amount of extra memory.
• Not stable, as it can swap equal elements.

Insertion Sort

• A simple sorting algorithm that works by iterating through the data one element at a time, inserting each element into its proper position in the sorted portion of the data.
• Time complexity: O(n^2) in worst and average cases, O(n) in best case.
• Space complexity: O(1) since it only uses a small amount of extra memory.
• Suitable for small data sets or almost-sorted data.

Selection Sort

• A simple sorting algorithm that works by selecting the smallest element from the unsorted portion of the data and moving it to the beginning of the sorted portion.
• Time complexity: O(n^2) in all cases.
• Space complexity: O(1) since it only uses a small amount of extra memory.
• Not suitable for large data sets due to its high time complexity.

Sorting Algorithms

Bubble Sort

• Repeatedly iterates through data, swapping adjacent elements if in wrong order
• Worst/average case time complexity: O(n^2), best case: O(n)
• Space complexity: O(1), uses minimal extra memory
• Not suitable for large data sets due to high time complexity

Merge Sort

• Divides data into smaller chunks, sorts each, and merges sorted chunks
• Time complexity: O(n log n) in all cases
• Space complexity: O(n), uses extra memory for temporary arrays
• Stable sorting algorithm, maintains relative order of equal elements

Quick Sort

• Selects pivot element, partitions data around pivot, recursively sorts sub-partitions
• Average/best case time complexity: O(n log n), worst case: O(n^2)
• Space complexity: Average/best case: O(log n), worst case: O(n)
• Not stable, can swap equal elements

Heap Sort

• Uses binary heap data structure to sort data
• Time complexity: O(n log n) in all cases
• Space complexity: O(1), uses minimal extra memory
• Not stable, can swap equal elements

Insertion Sort

• Iterates through data, inserting each element into its proper position in sorted portion
• Worst/average case time complexity: O(n^2), best case: O(n)
• Space complexity: O(1), uses minimal extra memory
• Suitable for small data sets or almost-sorted data

Selection Sort

• Selects smallest element from unsorted portion, moves it to beginning of sorted portion
• Time complexity: O(n^2) in all cases
• Space complexity: O(1), uses minimal extra memory
• Not suitable for large data sets due to high time complexity