Benchmark: Sorting Test: Tim Sort

Script Preparation code:

function randomNumber(min, max) {
	return Math.floor(Math.random() * (max + 1 + Math.abs(min))) + min
}
function newArr(lengths = 5, min = 0, max = 10) {
	let newArr = []
  for (let i = 0; i < lengths; i++) {
  	newArr.push(randomNumber(min, max))
  }
  return newArr
}


function insertionSort(arr, left, right) {
  for (let i = left + 1; i <= right; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

function merge(arr, l, m, r) {
  let len1 = m - l + 1;
  let len2 = r - m;
  let left = new Array(len1);
  let right = new Array(len2);
  for (let i = 0; i < len1; i++) left[i] = arr[l + i];
  for (let i = 0; i < len2; i++) right[i] = arr[m + 1 + i];

  let i = 0;
  let j = 0;
  let k = l;

  while (i < len1 && j < len2) {
    if (left[i] <= right[j]) {
      arr[k] = left[i];
      i++;
    } else {
      arr[k] = right[j];
      j++;
    }
    k++;
  }

  while (i < len1) {
    arr[k] = left[i];
    k++;
    i++;
  }

  while (j < len2) {
    arr[k] = right[j];
    k++;
    j++;
  }
}

function timSort(arr) {
  const MIN_RUN = 32;
  const n = arr.length;

  for (let i = 0; i < n; i += MIN_RUN) {
    insertionSort(arr, i, Math.min(i + MIN_RUN - 1, n - 1));
  }

  for (let size = MIN_RUN; size < n; size = 2 * size) {
    for (let left = 0; left < n; left += 2 * size) {
      let mid = left + size - 1;
      let right = Math.min(left + 2 * size - 1, n - 1);

      if (mid < right) {
        merge(arr, left, mid, right);
      }
    }
  }

  return arr;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);

    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

Tests:

Tim Sort
const sortedArr = timSort(newArr(200,-5000,5000))
Quick Sort
const sortedArr = quickSort(newArr(200,-5000,5000))

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Tim Sort
Quick Sort

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

**Benchmark Explanation**

The provided benchmark tests the performance of two sorting algorithms: Tim Sort and Quick Sort.

**Tim Sort**

*   **Overview**: Tim Sort is a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.
*   **Test Case**: The test case uses the `newArr` function to generate an array of 200 random integers between -5000 and 5000. This array is then passed to the `timSort` function for sorting.

**Quick Sort**

*   **Overview**: Quick sort is a divide-and-conquer algorithm that picks an element as pivot, partitions the array around it, and recursively sorts the sub-arrays.
*   **Test Case**: The test case uses the same `newArr` function to generate an array of 200 random integers between -5000 and 5000. This array is then passed to the `quickSort` function for sorting.

**Library Used:**

*   None

**Special JS Features/Syntax:**

None mentioned in the provided benchmark code.

**Comparison and Pros/Cons**

Both algorithms have their strengths and weaknesses:

*   **Tim Sort**: 
    *   Strengths:
        +   Stable sorting algorithm
        +   Adapts to input data size
    *   Weaknesses:
        +   Slower than Quick Sort for large datasets
        +   More complex implementation
*   **Quick Sort**:
    *   Strengths:
        +   Fastest on average, especially for large datasets
        +   Simple to implement
    *   Weaknesses:
        +   Worst-case performance can be poor (O(n^2))
        +   Not stable sorting algorithm

**Alternatives**

*   **Other Sorting Algorithms**: 
    *   Merge Sort: similar to Tim Sort, but uses a different approach
    *   Heap Sort: another divide-and-conquer algorithm
    *   Radix Sort: fast sorting algorithm for integers and strings
*   **Non-Comparison Sorting Algorithms**:
    *   Counting Sort: suitable for large datasets of integers or characters with a fixed range
    *   Bucket Sort: simple to implement, but may not be efficient for all data types

These alternatives can be used depending on the specific requirements and characteristics of the dataset being sorted.

Related benchmarks:

Sorting Test: Tim Sort (version: 0)

Tim Sort testing

Comparing performance of: Tim Sort vs Quick Sort

Created: 3 years ago by: Registered User

Jump to the latest result

Tim Sort

Quick Sort

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):