• Sorting is one of the most fundamental tasks in computer science.
• Different sorting algorithms have different time complexities and perform better in different scenarios.
• In this presentation, we’ll compare the performance of common sorting algorithms using statistical tools.

• Bubble Sort: Simple, but inefficient with a time complexity of \(O(n^2)\).
• Merge Sort: A divide-and-conquer algorithm with a time complexity of \(O(n \log n)\).
• Quick Sort: Another divide-and-conquer algorithm, but with better average performance, \(O(n \log n)\).
• Insertion Sort: Efficient for small datasets, \(O(n^2)\) in the worst case.

• Bubble Sort: Used in educational contexts to teach algorithm basics, but inefficient for large datasets.
• Merge Sort: Efficient for large datasets and commonly used in external sorting.
• Quick Sort: Often used in practical applications due to its average-case performance.
• Insertion Sort: Useful for small datasets or nearly sorted data.

The time complexity for each sorting algorithm can be written as:

\[ T(n)_{\text{Bubble Sort}} = O(n^2) \]

\[ T(n)_{\text{Merge Sort}} = O(n \log n) \]

\[ T(n)_{\text{Quick Sort}} = O(n \log n) \] —

We can model the comparison between Merge Sort and Quick Sort in terms of execution time:

\[ \text{Execution Time}_{\text{Merge Sort}} = \alpha n \log n \]

\[ \text{Execution Time}_{\text{Quick Sort}} = \beta n \log n \]

Where \(\alpha\) and \(\beta\) are constants for each algorithm.

The best-case time complexity for Quick Sort occurs when the pivot divides the array into two equal halves:

\[ T(n)_{\text{Best Case}} = O(n \log n) \]

In the worst case, where the pivot selection leads to unbalanced partitions, the time complexity is:

\[ T(n)_{\text{Worst Case}} = O(n^2) \]

On average, Quick Sort performs with time complexity:

\[ \text{Expected Comparisons}_{\text{Quick Sort}} = O(n \log n) \]

# Simulate sorting times for Bubble Sort, Merge Sort, and Quick Sort
set.seed(42)
bubble_sort_times <- rnorm(100, mean = 200, sd = 20)
merge_sort_times <- rnorm(100, mean = 50, sd = 5)
quick_sort_times <- rnorm(100, mean = 40, sd = 4)

# Combine data for plotting
execution_data <- data.frame(
  time = c(bubble_sort_times, merge_sort_times, quick_sort_times),
  algorithm = rep(c("Bubble Sort", "Merge Sort", "Quick Sort"), each = 100)
)

# Create a histogram
ggplot(execution_data, aes(x = time, fill = algorithm)) +
  geom_histogram(binwidth = 5, alpha = 0.6, position = "identity") +
  labs(title = "Distribution of Execution Times for Sorting Algorithms",
       x = "Execution Time (ms)", y = "Frequency") +
  theme_minimal()

• Merge Sort and Quick Sort are more efficient than Bubble Sort, with lower time complexity.
• The execution time for Merge Sort and Quick Sort is highly dependent on the dataset size.
• This analysis can be useful when choosing the best sorting algorithm for large datasets.