Algorithms are always a bit of a mystery to front-end engineers. This article explores the array.prototype.sort algorithm implementation by reading V8 source code.

Start by listing all the sorting algorithms you’ve used and heard of:

  • Quick sort
  • Bubble sort
  • Insertion sort
  • Merge sort
  • Heap sort
  • Hill sorting
  • Selection sort
  • Count sorting
  • Bucket sort
  • Radix sort
  • …

Which algorithm does sort use?

If you’ve searched the web for the source of Sort, you’ll probably be told to use insertion sort for arrays less than 10, and quicksort for arrays less than 10.

I thought so at first, but when I went to GitHub with the answer, I found it was not true.

First of all, I haven’t found the corresponding JS source code (the article says that the implementation logic is written in JS), because the new version of V8 source code has been modified to use V8 Torque. V8 Torque is a language created specifically for V8 development. It has a TypeScript like syntax (again, proving TypeScript’s value), and its compiler uses CodeStubAssembler to convert into efficient assembly code. The simple idea is to create an efficient typescript-like high-level language with the file suffix TQ.

Thanks to JustJavac

Second, when I started reading the source code, I didn’t find the code to use quicksort, nor did I find the constant value 10 to determine the length of the array.

All evidence suggests that previous source code reading articles are likely outdated.

So what sort algorithm does the latest version of V8 use?

Interpretation algorithm

The V8 engine abandoned quicksort after version XX because it was not a stable sorting algorithm and, in the worst case, time complexity was reduced to O(n^2). Instead, a hybrid sorting algorithm is used: TimSort. This algorithm was originally used in Python. Strictly speaking, it does not belong to any of the above 10 sorting algorithms. It belongs to a hybrid sorting algorithm: insert sort is used in small subarrays, and then merge sort is used to merge the ordered subarrays, and the time complexity is O(nlogn).

Combined with V8 source code, the specific implementation steps are as follows:

  1. If the array size is less than 2, return the array size.
  2. Start the cycle.
  3. Find an ordered subarray, called “run”, of length currentRunLength.
  4. Computes the minimum length of the merged sequence, minRunLength (this value dynamically varies from 32 to 64 depending on the array length).
  5. CurrentRunLength = minRunLength; currentRunLength = minRunLength; minRunLength = minRunLength; Push run into the stack pendingRuns.
  6. PendingRuns ensures that any three consecutive runs (run0, run1, run2) in the stack meet the requirements of run0>run1+run2 && run1>run2.
  7. If the remaining subarray is 0, end the loop.
  8. Merge all runs in the stack, and the sort is finished.

The source code interpretation

The source code path

/thrid_party/v8/builtins/array-sort.tq

The call stack

1386 ArrayPrototypeSort 1403 ArrayTimSort 1369 ArrayTimSortImpl 1260 ComputeMinRunLength // Computes minRunLength // while loop 1262 CountAndMakeRun // Calculate the current run length 1267 BinaryInsertionSort // add the run length 1274 MergeCollapse // add the pendingRuns 1281 MergeForceCollapse // Merge all runs in pendingRunsCopy the code

The core source

The TQ language is a bit different, but it shouldn’t be a problem to read if you have TypeScript basics. The following focuses on the interpretation of the source of three functions:

MinRunLength macro ComputeMinRunLength(nArg: Smi): Smi {let n: Smi = nArg; let r: Smi = 0; assert(n >= 0); / / constant divided by 2, to get the results between 32 and 64 while (n > = 64) {r = r | (n & 1); n = n >> 1; } const minRunLength: Smi = n + r; assert(nArg < 64 || (32 <= minRunLength && minRunLength <= 64)); return minRunLength; }Copy the code
Macro CountAndMakeRun(implicit Context: context, sortState: sortState)(lowArg: Smi, high: Smi); Smi { assert(lowArg < high); Const workArray = sortstate.workarray; const low: Smi = lowArg + 1; if (low == high) return 1; let runLength: Smi = 2; const elementLow = UnsafeCast<JSAny>(workArray.objects[low]); const elementLowPred = UnsafeCast<JSAny>(workArray.objects[low - 1]); Let order = sortState.Compare(elementLow, elementLowPred); const isDescending: bool = order < 0 ? true : false; let previousElement: JSAny = elementLow; For (let idx: Smi = low + 1; idx < high; ++idx) { const currentElement = UnsafeCast<JSAny>(workArray.objects[idx]); order = sortState.Compare(currentElement, previousElement); if (isDescending) { if (order >= 0) break; } else { if (order < 0) break; } previousElement = currentElement; ++runLength; } if (isDescending) { ReverseRange(workArray, lowArg, lowArg + runLength); } return runLength; }Copy the code
// Adjust pendingRuns so that if the stack length is greater than 3, Run [n]>run[n+1]+run[n+2] and run[n+1]>run2 SortState) { const pendingRuns: FixedArray = sortState.pendingRuns; while (GetPendingRunsSize(sortState) > 1) { let n: Smi = GetPendingRunsSize(sortState) - 2; if (! RunInvariantEstablished(pendingRuns, n + 1) || ! RunInvariantEstablished(pendingRuns, n)) { if (GetPendingRunLength(pendingRuns, n - 1) < GetPendingRunLength(pendingRuns, n + 1)) { --n; } MergeAt(n); } else if (pendingrunLength (pendingRuns, n) <= pendingrunLength (pendingRuns, n) n + 1)) { MergeAt(n); } else {break; }}}Copy the code

conclusion

The next time you’re interviewing for a front-end job, if the interviewer asks you an algorithm question, crack a smile and ask:

Do you know what algorithm Array’s sort uses? Would you like to know about TimSort?

Don’t blame the author if he or she embarrasses the interviewer and doesn’t get an offer

Reference:

The Great JavaScript Engineer is out, a book recommended by many technical experts to help you become a fully competent and holistic engineer. Click the link below to get started!

  • Taobao: detail.tmall.com/item.htm?id…
  • Jingdong: item.jd.com/12562349.ht…
  • Down-down: product.dangdang.com/27922044.ht…