Benchmark: Quick sort 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) { quick_sort(arr, 0, arr.length - 1); return arr; } function quick_sort(arr, low, high) { if (low < high) { // Get the partition index const pi = partition(arr, low, high); // Recursively sort elements before and after partition quick_sort(arr, low, pi - 1); quick_sort(arr, pi + 1, high); } } function partition(arr, low, high) { // Using last element as pivot const pivot = arr[high]; let i = low - 1; // Index of smaller element for (let j = low; j < high; j++) { // If current element is smaller than or equal to pivot if (arr[j] <= pivot) { i++; // Increment index of smaller element // Swap elements [arr[i], arr[j]] = [arr[j], arr[i]]; } } // Place pivot in its correct position [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1; } 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 (Android 14; Mobile; rv:130.0) Gecko/130.0 Firefox/130.0

Browser/OS: Firefox Mobile 130 on Android

View result in a separate tab

Test name	Executions per second
Quick Sort	628.8 Ops/sec
Merge Sort	2665.5 Ops/sec

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

LLMs can make mistakes. Check important info.

### Benchmark Overview

The provided benchmark compares the performance of two well-known sorting algorithms implemented in JavaScript: **Quick Sort** and **Merge Sort**. The benchmark measures the execution speed of both algorithms on a randomly generated array of integers.

### Test Cases

1. **Quick Sort**
   - **Implementation**: 
     - The `quickSort` function initiates the sorting process, and it works recursively via the `quick_sort` function.
     - The `partition` function is central to the Quick Sort's logic, where a pivot is selected (in this case, the last element), and the array is rearranged so that elements smaller than the pivot are moved to the left and those larger to the right.
     - It is an **in-place sort**, meaning it requires a small, constant amount of additional storage space.

- **Pros**:
     - Generally faster (average O(n log n) time complexity).
     - In-place sorting conserves memory.
   
   - **Cons**:
     - Worse performance in the worst-case scenario (O(n^2)), which can occur with already sorted or reverse-sorted arrays if not optimized (like using randomness in pivot selection).
     - Recursive depth can lead to stack overflow with very large arrays.

2. **Merge Sort**
   - **Implementation**:
     - The `mergeSort` function divides the input array into smaller arrays until it reaches arrays of length one.
     - The `merge` function is then used to combine those sorted arrays back into a single sorted array.
     - It’s a **divide-and-conquer** algorithm that consistently performs well.

- **Pros**:
     - Always runs in O(n log n) time complexity, providing stable sorting.
     - Supports large lists better due to its predictable performance.
   
   - **Cons**:
     - Requires additional space for the temporary arrays, making it less memory-efficient, particularly for large datasets.
     - Not an in-place sort.

### Benchmark Results

- **Executions Per Second**:
  - **Merge Sort**: Approximately **4597.58**, indicating a higher throughput in execution.
  - **Quick Sort**: Approximately **447.44**, which is significantly lower.
  
This stark difference in performance suggests that for the given input dataset of size 1000, the implementation of Merge Sort outperformed Quick Sort in this benchmark.

### Considerations

- **Size of Input Array**: The performance difference in execution speed can vary based on the input size and the nature of the input (random, sorted, etc.). 
- **JavaScript Execution Environment**: The benchmark is conducted in a browser environment (specifically Chrome 124 on Linux), which might influence performance due to different JavaScript engine optimizations.
- **Use Cases**: If memory usage is a primary concern and the input size is moderate, Quick Sort would be preferable. For large datasets or when a stable sort is necessary, Merge Sort should be favored.

### Alternatives

- **Heap Sort**: Another comparison could include Heap Sort, which offers O(n log n) performance and is also an in-place sorting algorithm. However, it is typically slower in practice due to cache inefficiencies.
- **Tim Sort**: This hybrid sorting algorithm, used in Python and Java, combines Merge Sort and Insertion Sort and offers good performance across different kinds of data.
- **Native Array Sort**: In JavaScript, using the built-in `.sort()` method could be an alternative, which is often optimized and utilizes a combination of sorting techniques.

In summary, the benchmark serves as a practical comparison of Quick Sort and Merge Sort, highlighting their strengths and weaknesses in terms of speed and memory efficiency within a JavaScript execution context.

Related benchmarks:

Quick sort 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):