JavaScript의 sort는 어떤 정렬 알고리즘을 사용할까?

CS 스터디에서 sorting에 대해서 얘기를 하던 중, java에서는 sort 내장 메서드가 merge sort를 사용한다는 얘기를 들었다. JavaScript에서도 sort는 매우 자주 사용하는 메서드라, 어떤 정렬 알고리즘을 사용하는지 궁금해져 찾아보았다. 그 결과 JavaScript는 놀랍게도, 엔진에 따라서 다른 정렬 알고리즘을 사용한다는 사실을 알게되었다. ECMAscript 에 어떤 알고리즘을 써야하는지 특정하지 않았기 때문에, 브라우저마다 다른 정렬 알고리즘을 사용하는 것이다. 그래서 각 엔진은 어떤 정렬 알고리즘을 사용하는지 궁금해져 정리해보고자 했다.

---

1️⃣ V8 엔진

출처 - v8 기술 블로그

제일 먼저 알아볼 것은 Chrome 브라우저와 nodeJS 의 V8 엔진이다.
v8 엔진은 과거와 현재 다른 정렬 알고리즘을 사용하고 있다.

⛅ 우선 과거, V8 v7.0 및 Chrome 70 전에는 퀵 정렬과 삽입 정렬을 혼합하여 사용하였다.

• 길이가 10 미만인 array의 경우 삽입 정렬
• 그 외에는 퀵 정렬을 사용
• 퀵 정렬에서 array를 분할해가는 과정에서 10 미만의 array가 생길 경우에도 삽입 정렬을 사용

 

🤔 왜 굳이 두 정렬을 혼용하여 사용하였을까?

- 퀵 정렬의 경우 분할한 뒤에 재귀 호출하기 때문에 오버헤드를 발생시키때문에, 짧은 array의 경우 삽입 정렬이 더욱 효과적이기 때문이다!

🍓퀵 정렬의 장점과 단점

• 장점
  • 정렬하고자 하는 배열 안에서 교환하는 방식(제자리 정렬)이므로, 별도의 메모리 공간을 필요로 하지 않는다
• 단점
  • 불안정 정렬(Unstable Sort) 이다
  • pivot을 최솟/최댓값으로 선택하는 경우나 이미 정렬되어 있는 경우 최악의 시간 복잡도를 가진다.(O(n^2)).
    • median of three 방식을 선택하여 첫번째, 중간, 그리고 마지막 값 중에서 중간값을 pivot으로 사용하는 방식을 사용했다.

 

🔆현재

V8 v7.0 및 Chrome 70 이후부터는 Timsort 라는 정렬 알고리즘을 사용하고 있다. Timsort 정렬 알고리즘에서는, 작은 단위일 때는 여전히 삽입 정렬을 사용하지만, 그보다 큰 array에서는 퀵 정렬 대신 합병(merge) 정렬을 사용한다.

Timsort를 사용하게된 이유
quick정렬은 불안정 정렬인 것에 반해, v8 bug tracker는 안정 정렬이 필요로 했기 때문이다. 그래서 현재는 안정 정렬인 Timsort를 사용한다.

🙄Timsort 이해한 대로 간단 요약
완전히 이해하기엔 아직 역부족이다...
- 앞서도 얘기했듯이, array의 길이가 짧을 때는 삽입 정렬의 효율이 매우 좋다.
- 전체를 작은 덩어리로 잘라 각각의 덩어리를 삽입 정렬로 정렬한 뒤, 합병 정렬로 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다.
- 2x개씩 잘라서 각각을 삽입 정렬로 정렬하면 덩어리별 xx개 병합 동작이 생략되어 그만큼 속도가 빨라진다.
- 최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 O(nlogn) 이다.
Timsort 관련하여 읽기 좋은 글

2️⃣ Spidermonkey 엔진

출처 - Searchfox
다음으로 알아볼 것은 mozilla/firefox 의 Spidermonkey 엔진이다.

• 삽입과 합병 정렬을 혼용하여 사용한다.
• array의 길이가 24 이하일 때는 삽입 정렬을 사용한다.
• 그 이상의 길이의 array에서는 합병 정렬을 사용한다.

마찬가지로 짧은 길이일 때는 삽입 정렬을 사용했다. 

function MergeSort(array, len, comparefn) {
  assert(IsPackedArray(array), "array is packed");
  assert(array.length === len, "length mismatch");
  assert(len > 0, "array should be non-empty");

  // Insertion sort for small arrays, where "small" is defined by performance
  // testing.
  if (len < 24) {
    InsertionSort(array, 0, len - 1, comparefn);
    return array;
  }

  // We do all of our allocating up front
  var lBuffer = array;
  var rBuffer = [];

  // Use insertion sort for initial ranges.
  var windowSize = 4;
  for (var start = 0; start < len - 1; start += windowSize) {
    var end = std_Math_min(start + windowSize - 1, len - 1);
    InsertionSort(lBuffer, start, end, comparefn);
  }

  for (; windowSize < len; windowSize = 2 * windowSize) {
    for (var start = 0; start < len; start += 2 * windowSize) {
      // The midpoint between the two subarrays.
      var mid = start + windowSize - 1;

      // To keep from going over the edge.
      var end = std_Math_min(start + 2 * windowSize - 1, len - 1);

      Merge(lBuffer, rBuffer, start, mid, end, comparefn);
    }

    // Swap both lists.
    var swap = lBuffer;
    lBuffer = rBuffer;
    rBuffer = swap;
  }
  return lBuffer;
}

 

3️⃣ webkit 엔진

출처 - webkit 소스 코드
다음은 webkit/safari 의 경우이다.

• string의 경우 버킷(bucket) 정렬 사용한다.
  • 버킷 정렬: 수많은 버킷에 배열 요소를 분산시킴으로써 동작하는 정렬 알고리즘
• string이 아닐 경우 합병(merge) 정렬 이용한다.

자바스크립트의 sort는 기본적으로 사전식 정렬을 한다. 그래서 숫자를 정렬할 때도 compare 함수를 전달하지 않으면 string처럼 사전과 같이 정렬을 한다. 그 특징이 여기에서도 드러나있다. comparator가 undefined일 경우 isStringsort가 true가 되어 sortBucketSort 함수를 호출하여 버킷 정렬을 하고, comparator가 존재할 경우 sortMergeSort 함수를 호출하여 합병 정렬을 한다. 

function sort(comparator)
{
    "use strict";

    var isStringSort = false;
    if (comparator === @undefined)
        isStringSort = true;
    else if (!@isCallable(comparator))
        @throwTypeError("Array.prototype.sort requires the comparator argument to be a function or undefined");

    var receiver = @toObject(this, "Array.prototype.sort requires that |this| not be null or undefined");
    var receiverLength = @toLength(receiver.length);

    // For compatibility with Firefox and Chrome, do nothing observable
    // to the target array if it has 0 or 1 sortable properties.
    if (receiverLength < 2)
        return receiver;

    var compacted = [ ];
    var sorted = null;
    var undefinedCount = @sortCompact(receiver, receiverLength, compacted, isStringSort);

    if (isStringSort) {
        sorted = @newArrayWithSize(compacted.length);
        @sortBucketSort(sorted, 0, compacted, 0);
    } else
        sorted = @sortMergeSort(compacted, comparator);

    @sortCommit(receiver, receiverLength, sorted, undefinedCount);
    return receiver;
}

---

같은 sort를 처리하는 방법이 어찌 보면 다 다른 것처럼 보일 수 있지만, 작은 배열의 경우 삽입을 사용하고, 길이가 길어지면 quick이나 merge를 기반으로 한다는 점에서는 비슷했다. 다른 언어의 경우는 어떨지도 궁금해져 찾아보니 자바는 merge sort,  c++ 의 경우 quick sort, 파이썬의 경우 Timsort 를 사용한다고 한다. 언어 전반적으로 sort 의 정렬 알고리즘은 크게 다름 없이 비슷하게 사용함을 알 수 있었다.