Benchmark: Quick Sort 2 vs Merge Sort

HTML Preparation code:

<!--your preparation HTML code goes here-->

Script Preparation code:

var arr = new Array(1000);
for (let i = 0; i < size; i++) {
    arr[i] = Math.floor(Math.random() * 1000000); // Random numbers between 0 and 999999
}

Tests:

Quick Sort
function quickSort(arr) { if (arr.length <= 1) return arr; const pivot = arr[Math.floor(arr.length / 2)]; const left = []; const right = []; const equal = []; for (let element of arr) { if (element < pivot) { left.push(element); } else if (element > pivot) { right.push(element); } else { equal.push(element); } } return [...quickSort(left), ...equal, ...quickSort(right)]; } quickSort(arr)
Merge Sort
function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { const result = []; let leftIndex = 0; let rightIndex = 0; while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]); leftIndex++; } else { result.push(right[rightIndex]); rightIndex++; } } return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex)); } mergeSort(arr)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Quick Sort
Merge Sort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 months ago)

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/124.0.0.0 Safari/537.36

Browser/OS: Chrome 124 on Linux

View result in a separate tab

Test name	Executions per second
Quick Sort	56294.4 Ops/sec
Merge Sort	4548.6 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated 3 months ago):

LLMs can make mistakes. Check important info.

The benchmark defined in the provided JSON compares the performance of two sorting algorithms: Quick Sort and Merge Sort. Both algorithms are commonly used for sorting arrays but have different methodologies and performance characteristics.

### Benchmark Overview

#### Description of Algorithms:
1. **Quick Sort**:
   - **Implementation**: The Quick Sort algorithm implemented here selects a pivot (the middle element of the array) and partitions the array into three arrays based on the pivot: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. It then recursively sorts the left and right arrays and combines them.
   - **Performance**: Quick Sort has an average time complexity of \(O(n \log n)\) but can degrade to \(O(n^2)\) in the worst case (such as when the pivot selection yields unbalanced partitions). It is generally faster than Merge Sort in practice on average and uses less memory since it operates in place.

2. **Merge Sort**:
   - **Implementation**: This implementation divides the array into two halves, recursively sorts each half, and then merges the two sorted halves back together. The merging step involves comparing elements from the two halves and combining them into a sorted structure.
   - **Performance**: Merge Sort consistently performs at \(O(n \log n)\) for all cases (best, average, worst). However, it is less efficient than Quick Sort in terms of memory because it requires additional space proportional to the array size for storing temporary arrays during the merge phase.

### Comparison of Options
- **Execution Speed**:
  - The benchmark results clearly indicate that Quick Sort is significantly faster than Merge Sort, achieving approximately **56,294 executions per second** versus **4,548 executions per second** for Merge Sort.
  
- **Space Complexity**:
  - Quick Sort can often be implemented to use less auxiliary space, while Merge Sort's requirement for additional temporary arrays can be a considerable downside.
  
- **Performance in Practice**:
  - While Quick Sort may outperform Merge Sort on average due to its lower constant factors, it's crucial to note that Merge Sort guarantees stability (it preserves the order of equal elements) and performs consistently better with large datasets, especially when the datasets do not fit in memory (external sorting).

### Considerations
- **Stability**: If the order of equal elements must be maintained, Merge Sort is the better choice. Quick Sort is not stable, and elements with equal keys may not keep their original order.
- **Data Characteristics**: The choice between these two algorithms can depend on the types of data being sorted, the system architecture, and memory constraints.
- **Adaptive Sorts**: Other alternatives include adaptive sorting algorithms such as TimSort (used in Python) which incorporates properties from both algorithms and is particularly efficient for partially-sorted data.

### Other Alternatives
Besides Quick Sort and Merge Sort, there are several other sorting algorithms commonly used:
- **Bubble Sort**: Very simple but inefficient for large datasets (\(O(n^2)\)).
- **Insertion Sort**: More efficient than Bubble Sort, especially for small or partially sorted arrays (\(O(n \text{ or } n^2)\)).
- **Heap Sort**: In-place and uses a binary heap data structure, maintaining \(O(n \log n)\) performance.
- **Radix Sort**: A non-comparison-based sorting algorithm that can be very efficient for integers and fixed-size strings.

In conclusion, the choice between Quick Sort and Merge Sort depends on the specific needs of the application, the characteristics of the data, and the environment in which sorting will take place. The benchmark results favor Quick Sort in terms of execution speed for the tested scenarios.

Related benchmarks:

Quick Sort 2 vs Merge Sort (version: 1)

Comparing performance of: Quick Sort vs Merge Sort

Created: 3 months ago by: Guest

Jump to the latest result

Quick Sort

Merge Sort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gpt-4o-mini, generated 3 months ago):