holsee

Some notes on IntroSort…

Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since both algorithms it uses are comparison sorts, it too is a comparison sort.

Introsort was invented by David Musser in Musser (1997), in which he also introduced introselect, a hybrid selection algorithm based on quickselect (a variant of quicksort), which falls back to median of medians and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the purpose of providing generic algorithms for the C++ Standard Library which had both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.

Source: Wikipedia | David Musser Paper ‘Musser (1997)’

.NET 4.5 introduces Introsort in place of Quicksort

In the Microsoft .NET Framework 4.5, an Introsort implementation is used instead of simple QuickSort.

If the sort is not successfully completed, the results are undefined. This method uses the introspective sort (introsort) algorithm as follows:

• If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.
• If the number of partitions exceeds 2 * Log_N, where N is the range of the input array, it uses a Heapsort algorithm.

1	IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));

• Otherwise, it uses a Quicksort algorithm.

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

For arrays that are sorted by using the Heapsort and Quicksort algorithms, in the worst case, this method is an O(_n log _n) operation, where _n is the Length of array.

You can view the full source for .NET 4.5 sorting implementation here: .NET 4.5.1 QuickSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

private void IntroSort(int lo, int hi, int depthLimit)
{
    while (hi > lo)
    {
        int partitionSize = hi - lo + 1;
        if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold /* 32 */)
        {
            if (partitionSize == 1)
            {
                return;
            }
            if (partitionSize == 2)
            {
                SwapIfGreaterWithItems(lo, hi);
                return;
            }
            if (partitionSize == 3)
            {
                SwapIfGreaterWithItems(lo, hi-1);
                SwapIfGreaterWithItems(lo, hi);
                SwapIfGreaterWithItems(hi-1, hi);
                return;
            }

            InsertionSort(lo, hi);
            return;
        }

        if (depthLimit == 0)
        {
            Heapsort(lo, hi);
            return;
        }
        depthLimit--;

        int p = PickPivotAndPartition(lo, hi);
        IntroSort(p + 1, hi, depthLimit);
        hi = p - 1;
    }
}

You can view the latest (MIT licensed) Mono implemention on Github: Mono.C5 Sorting.cs

Quicksort, also known as partition-exchange sort, uses these steps.

1. Choose any element of the array to be the pivot.
2. Divide all other elements (except the pivot) into two partitions.
   - All elements less than the pivot must be in the first partition.
   - All elements greater than the pivot must be in the second partition.
3. Use recursion to sort both partitions.
4. Join the first sorted partition, the pivot, and the second sorted partition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void swap(int *a, int *b) {
  int t=*a;
  *a=*b;
  *b=t;
}

void sort(int arr[], int beg, int end) {
  if (end > beg + 1) {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r) {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    // swapping elements within the array 
    // to avoid the memory allocation of more arrays.
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function sort(array, less) {

  function swap(i, j) {
    var t=array[i];
    array[i]=array[j];
    array[j]=t
  }

  function quicksort(left, right) {
    if (left < right) {
      var pivot = array[(left + right) >> 1];
      var left_new = left, right_new = right;
      do {
        while (less(array[left_new], pivot)
          left_new++;
        while (less(pivot, array[right_new])
          right_new--;
        if (left_new  <= right_new)
          swap(left_new++, right_new--);
      } while (left_new  <= right_new);
      quicksort(left, right_new);
      quicksort(left_new, right);
    }
  }

  quicksort(0, array.length-1);
  return array;
}

1
2
3
4
5
6
7
8
9
10
11

Array.prototype.quick_sort = function ()
{
    if (this.length <= 1)
      return this;

    var pivot = this[Math.round(this.length / 2)];

    return this.filter(function (x) { return x <  pivot }).quick_sort().concat(
           this.filter(function (x) { return x == pivot })).concat(
           this.filter(function (x) { return x >  pivot }).quick_sort());
}

1
2
3
4
5
6
7
8
9

class Array
  def quick_sort
    return self if length <= 1
    pivot = sample
    group = group_by{ |x| x <=> pivot }
    group.default = []
    group[-1].quick_sort + group[0] + group[1].quick_sort
  end
end

1
2
3
4
5
6

class Array
  def quick_sort
    h, *t = self
    h ? t.partition { |e| e < h }.inject { |l, r| l.quick_sort + [h] + r.quick_sort } : []
  end
end

You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at the last element in the key. You move that item into the end of the queue which corresponds to that element. When you are finished looping you concatenate all the queues together into another sequence. You then reapply the procedure described but look at the second last element in the key. You keep doing this until you have looped over every key. When you complete this process the resulting sequence will be sorted as described above.

Let n_i be the number of items in the sequence to be sorted. N is number of integers that each key element can take. Let n_k be the number of keys in each item.

The total time to sort the sequence is thus O(n_k(n_i + N)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function mergesort(list){
  if (list.length <= 1)
    return list;

  var mid = Math.floor(list.length / 2),
    left  = list.slice(0, mid),
    right = list.slice(mid, list.length);

  return merge(mergesort(left), mergesort(right))
}

function merge(left, right){
  var sorted = [];
  while (left && left.length > 0 && right && right.length > 0){
    var b = left[0] <= right[0];
    sorted.push(b? left[0]: right[0]);
    // remove the element which was added to the sorted array
    b? left.splice(0, 1): right.splice(0, 1);
  }
  return sorted.concat(left, right);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def mergesort(list)
  return list if list.size <= 1
  mid = list.size / 2
  left  = list[0, mid]
  right = list[mid, list.size-mid]
  merge(mergesort(left), mergesort(right))
end

def merge(left, right)
  sorted = []
  until left.empty? or right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end
  sorted.concat(left).concat(right)
end

Coursera – Functional Programming Principles in Scala

About the Course

This is a follow-on for the Coursera class “Principles of Functional Programming in Scala”, which so far had more than 100’000 inscriptions over two iterations of the course, with some of the highest completion rates of any massive open online course worldwide.

The aim of the second course is to teach the principles of reactive programming. Reactive programming is an emerging discipline which combines concurrency and event-based and asynchronous systems. It is essential for writing any kind of web-service or distributed system and is also at the core of many high-performance concurrent systems. Reactive programming can be seen as a natural extension of higher-order functional programming to concurrent systems that deal with distributed state by coordinating and orchestrating asynchronous data streams exchanged by actors.

In this course you will discover key elements for writing reactive programs in a composable way. You will find out how to apply these building blocks in the construction of event-driven systems that are scalable and resilient.

The course is hands on; most units introduce short programs that serve as illustrations of important concepts and invite you to play with them, modifying and improving them. The course is complemented by a series of assignments, which are also programming projects.