Benchmark: Quick Sort 2 vs Merge Sort fixed

HTML Preparation code:

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

Script Preparation code:

var arr = new Array(1000);
for (let i = 0; i < 1000; 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: one year ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser/OS: Chrome 131 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Quick Sort	16530.9 Ops/sec
Merge Sort	5869.1 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated one year ago):

LLMs can make mistakes. Check important info.

The benchmark described tests the performance of two sorting algorithms: **Quick Sort** and **Merge Sort**. The benchmark measures how many times each sorting function can be executed per second using randomly generated arrays of integers.

### Benchmark Options Compared

1. **Quick Sort**
   - **Implementation**: The quick sort algorithm selects a pivot element and partitions the array into three arrays: elements less than the pivot (`left`), elements greater than the pivot (`right`), and elements equal to the pivot (`equal`). It recursively sorts the left and right arrays and concatenates the result.
   - **Performance**: According to the benchmark results, Quick Sort can execute approximately **16,531 times per second**.
   - **Pros**:
     - Average time complexity is \(O(n \log n)\), making it relatively efficient for large datasets.
     - Generally performs well in practice for diverse datasets and is often faster than other algorithms like Merge Sort.
   - **Cons**:
     - Worst-case time complexity is \(O(n^2)\) when the smallest or largest element is frequently chosen as the pivot (e.g., when the input is already sorted).
     - Requires additional memory space for the recursive stack, which can be significant for large arrays.

2. **Merge Sort**
   - **Implementation**: Merge Sort divides the array into two halves, recursively sorting each half, and then merges the two sorted halves into a single sorted array.
   - **Performance**: The benchmark shows that Merge Sort can execute approximately **5,869 times per second**.
   - **Pros**:
     - Consistent \(O(n \log n)\) time complexity for worst-case, average-case, and best-case scenarios, making it reliable for performance.
     - Stable sorting algorithm, meaning it maintains the order of equal elements.
   - **Cons**:
     - Requires \(O(n)\) additional space for the temporary arrays during the merging process, which can increase memory usage for large datasets.
     - Typically slower than Quick Sort in practice due to the overhead of merging operations.

### Other Considerations
- **Memory Usage**: Quick Sort is generally more memory efficient in terms of auxiliary space compared to Merge Sort, when using an in-place implementation.
- **Stability**: Merge Sort is stable, which can be important when sorting complex data structures where the relative order of elements with equal keys must be preserved.

### Alternatives to Consider
1. **Heap Sort**: Another efficient sorting algorithm with \(O(n \log n)\) time complexity. It is not stable but uses \(O(1)\) additional memory. However, it tends to be slower than Quick Sort and Merge Sort in practical scenarios.
2. **Tim Sort**: A hybrid sorting algorithm derived from Merge Sort and Insertion Sort, which is the default in Python. It is stable and performs very well on real-world data.
3. **Insertion Sort**: More efficient for small or mostly sorted arrays, as it has a lower overhead compared to more complex algorithms, but has a worst-case complexity of \(O(n^2)\).

In summary, the benchmark provides insight into the performance of different sorting strategies, highlighting their strengths and weaknesses, which are critical when selecting the appropriate sorting method for a given context in software development.

Related benchmarks:

Quick Sort 2 vs Merge Sort fixed (version: 1)

Comparing performance of: Quick Sort vs Merge Sort

Created: one year ago by: Guest

Jump to the latest result

Quick Sort

Merge Sort

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gpt-4o-mini, generated one year ago):