CODEWITHSUNDEEP
dart
user11496192
user11496192

Reputation:

What is the algorithm used in sort method in dart?

I found out that dart language has a built-in sort method in List class and I would like to know what is the algorithm they used in this method and what is the Big O notation of it?

Upvotes: 10

Views: 3666

Answers (2)

julemand101
julemand101

Reputation: 31279

I found out that dart language has a built-in sort method in List class and I would like to know what is the algorithm they used in this method and what is the Big O notation of it?

If we take a look inside the SDK we can find the following implementation of the sort method on List:

  void sort([int compare(E a, E b)]) {
    Sort.sort(this, compare ?? _compareAny);
  }

https://github.com/dart-lang/sdk/blob/b86c6e0ce93e635e3434935e31fac402bb094705/sdk/lib/collection/list.dart#L340-L342

Which just forward the sorting to the following internal helper class:

https://github.com/dart-lang/sdk/blob/a75ffc89566a1353fb1a0f0c30eb805cc2e8d34c/sdk/lib/internal/sort.dart

Which has the following comment about the sorting algorithm:

/**
 * Dual-Pivot Quicksort algorithm.
 *
 * This class implements the dual-pivot quicksort algorithm as presented in
 * Vladimir Yaroslavskiy's paper.
 *
 * Some improvements have been copied from Android's implementation.
 */

This sorting algorithm is actually the same used in Java (at least Java 7):

http://www.docjar.com/html/api/java/util/DualPivotQuicksort.java.html

Here we can see that the O-notation is mostly O(n log(n)):

    * This class implements the Dual-Pivot Quicksort algorithm by
    * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
    * offers O(n log(n)) performance on many data sets that cause other
    * quicksorts to degrade to quadratic performance, and is typically
    * faster than traditional (one-pivot) Quicksort implementations.

For more details you can read the paper by the designer of the Dual-Pivot Quicksort algorithm:

https://web.archive.org/web/20151002230717/http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

But, also please note that Dart also has the following constant:

  // When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will
  // be sorted by an insertion sort.
  static const int _INSERTION_SORT_THRESHOLD = 32;
...
  static void _doSort<E>(
      List<E> a, int left, int right, int compare(E a, E b)) {
    if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
      _insertionSort(a, left, right, compare);
    } else {
      _dualPivotQuicksort(a, left, right, compare);
    }
  }

So for small lists, it makes more sense to use the traditional insertion sort algorithm which has a worst case big O of О(n^2). But since the input are very small, it is properly faster than the Dual-Pivot Quicksort algorithm.

Upvotes: 26

user2740650
user2740650

Reputation: 1753

At https://dartpad.dartlang.org/, try the following code. I can't answer your question about what the implementation is under the covers, but you can bet it's O(n log n).

I'm using an answer because I can't supply code in a comment easily.

void main() {
  Map<String, int> map = {'a': 1, 'b': 2};

  List<String> list = ['banana', 'apple', 'age', 'bob'];

  list.sort((String a, String b) => a.compareTo(b));
  print(list);
}

BTW list.sort(); would give the same results since that custom comparitor is the same as the default.

Upvotes: 0

Related Questions