Benchmark: Lodash_4.17.21.sortBy vs .sort vs custom insertion vs custom quick

HTML Preparation code:

<script src='https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.21/lodash.min.js'></script>

Script Preparation code:

var arr = [{
  name: "Ваня",
  date: "2024-12-01 18:00",
  curr: "RUB",
  level: 12,
},
{
  name: "Маня",
  date: "2024-12-01 02:00",
  curr: "KZT",
  level: 3,
},
{
  name: "Петя",
  date: "2024-12-01 12:00",
  curr: "USD",
  level: 7,
},
{
  name: "Вика",
  date: "2024-12-01 05:00",
  curr: "RUB",
  level: 9,
},
{
  name: "Лера",
  date: "2024-12-01 11:00",
  curr: "RUB",
  level: 2,
},
{
  name: "Каша",
  date: "2024-12-01 15:00",
  curr: "KZT",
  level: 10,
},
{
  name: "Паша",
  date: "2024-12-01 17:00",
  curr: "USD",
  level: 1,
},
{
  name: "Даша",
  date: "2024-12-01 10:00",
  curr: "RUB",
  level: 8,
},
{
  name: "Вера",
  date: "2024-12-01 00:00",
  curr: "RUB",
  level: 5,
},
{
  name: "Саша",
  date: "2024-12-01 14:00",
  curr: "USD",
  level: 11,
},
{
  name: "Маша",
  date: "2024-12-01 10:00",
  curr: "KZT",
  level: 4,
},
{
  name: "Ваня",
  date: "2024-12-01 15:00",
  curr: "USD",
  level: 6,
},
];

var CURR_ORDER = {
  RUB: 1,
  USD: 2,
  KZT: 3,
};

var CONDITIONS = [
  (a, b) => CURR_ORDER[a.curr] - CURR_ORDER[b.curr],
  (a, b) => new Date(a.date) - new Date(b.date),
];

var compare = (conditions) => (a, b) => {
  for (let i = 0; i < conditions.length; i++) {
    const condition = conditions[i];
    const type = typeof condition;
    if (type === "string") {
      if (typeof a[condition] === "string") {
        const result = a[condition].localeCompare(b[condition]);
        if (!result) continue;
        return result;
      } else if (typeof a[condition] === "number") {
        const result = a[condition] - b[condition];
        if (!result) continue;
        return result;
      }
    } else if (type === "function") {
      const result = condition(a, b);
      if (!result) continue;
      return result;
    }
  }

  return 0;
};

var stdSort = (arr, conditions) => {
  const newArr = [...arr];
  newArr.sort(compare);
  return newArr;
};

var insertionSort = (arr, conditions) => {
  const newArr = [...arr];

  for (let i = 1, l = newArr.length; i < l; i++) {
    const current = arr[i];
    let j = i;
    const comp = compare(conditions);
    while (j > 0 && comp(newArr[j - 1], current)) {
      newArr[j] = newArr[j - 1];
      j--;
    }
    newArr[j] = current;
  }
  return newArr;
};

var partition = (arr, start, end, compare) => {
  const pivotValue = arr[end];
  let pivotIndex = start;


  for (let i = start; i < end; i++) {
    if (compare(arr[i], pivotValue) < 0) {
      [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
      pivotIndex++;
    }
  }

  [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]];
  return pivotIndex;
};

var quickSortIterative = (arr, conditions) => {
  const newArr = [...arr];
  const stack = [0, arr.length - 1];
  const comp = compare(conditions);

  while (stack[stack.length - 1] >= 0) {
    end = stack.pop();
    start = stack.pop();

    pivotIndex = partition(newArr, start, end, comp);

    if (pivotIndex - 1 > start) {
      stack.push(start);
      stack.push(pivotIndex - 1);
    }

    if (pivotIndex + 1 < end) {
      stack.push(pivotIndex + 1);
      stack.push(end);
    }
  }

  return newArr;
};

Tests:

Lodash_4.17.21.sortBy
_.sortBy(arr, [(o) => CURR_ORDER[o.curr], (o) => new Date(o.date)]);
stdSort
stdSort(arr, CONDITIONS);
InsertionSort
insertionSort(arr, CONDITIONS);
QuickSort
quickSortIterative(arr, CONDITIONS);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Lodash_4.17.21.sortBy
stdSort
InsertionSort
QuickSort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 YaBrowser/24.1.0.0 Safari/537.36

Browser/OS: Yandex Browser 24 on Windows

View result in a separate tab

Test name	Executions per second
Lodash_4.17.21.sortBy	95265.9 Ops/sec
stdSort	695100.0 Ops/sec
InsertionSort	45205.5 Ops/sec
QuickSort	42748.7 Ops/sec

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

LLMs can make mistakes. Check important info.

To determine which sorting algorithm is the fastest, I'll analyze the benchmark results provided.

**Benchmark Results Analysis**

1. **stdSort**: 695100 executions per second (EPS) on Yandex Browser 24 on Windows desktop. This suggests that **stdSort** is the fastest among the four algorithms tested.
2. **Lodash_4.17.21.sortBy**: 95265 EPS, which is significantly slower than **stdSort**. This implies that Lodash's `sortBy` function is not optimized for performance in this specific test case.
3. **InsertionSort**: 45205 EPS, making it the slowest among the four algorithms. Insertion sort has a time complexity of O(n^2), which explains its poor performance in this benchmark.
4. **quickSortIterative**: 42748 EPS, which is slower than **stdSort** but faster than **InsertionSort**. This suggests that QuickSort, with some optimizations like iterative partitioning, can be competitive in certain cases.

**Conclusion**

Based on the benchmark results, **stdSort** appears to be the fastest sorting algorithm among the four tested, followed closely by **quickSortIterative**. Lodash's `sortBy` function is not optimized for performance in this specific test case, and Insertion Sort remains one of the slowest sorting algorithms due to its quadratic time complexity.

Please note that benchmark results can vary depending on the input data, system configuration, and other factors. These observations are based on the provided benchmark results and may not be universally applicable.

Related benchmarks:

Lodash_4.17.21.sortBy vs .sort vs custom insertion vs custom quick (version: 0)

Comparing performance of: Lodash_4.17.21.sortBy vs stdSort vs InsertionSort vs QuickSort

Created: 2 years ago by: Guest

Jump to the latest result

Lodash_4.17.21.sortBy

stdSort

InsertionSort

QuickSort

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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