AlgoViz: Interactive Algorithm Visualization Tool

Intro Sort

Category: Sorting | Time: O(n log n) | Space: O(log n)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function introSort(arr) {
  let maxdepth = Math.floor(Math.log2(arr.length)) * 2;
  introsort_helper(arr, 0, arr.length - 1, maxdepth);
  return arr;
}

function introsort_helper(arr, begin, end, maxdepth) {
  if (end - begin < 16) {
    insertionSort(arr, begin, end);
    return;
  }
  if (maxdepth === 0) {
    heapSort(arr, begin, end);
    return;
  }
  let p = partition(arr, begin, end);
  introsort_helper(arr, begin, p - 1, maxdepth - 1);
  introsort_helper(arr, p + 1, end, maxdepth - 1);
}

function partition(arr, begin, end) {
  let pivot = arr[end];
  let i = begin - 1;
  for (let j = begin; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[j]];
    }
  }
  [arr[i + 1], arr[end]] = [arr[end], arr[i + 1]];
  return i + 1;
}

function heapSort(arr, begin, end) {
  let n = end - begin + 1;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i, begin);
  }
  for (let i = n - 1; i > 0; i--) {
    [arr[begin], arr[begin + i]] = [arr[begin + i], arr[begin]];
    heapify(arr, i, 0, begin);
  }
}

function heapify(arr, n, i, offset) {
  let largest = i;
  let l = 2 * i + 1;
  let r = 2 * i + 2;
  if (l < n && arr[offset + l] > arr[offset + largest]) largest = l;
  if (r < n && arr[offset + r] > arr[offset + largest]) largest = r;
  if (largest !== i) {
    [arr[offset+i], arr[offset+largest]] = [arr[offset+largest], arr[offset+i]];
    heapify(arr, n, largest, offset);
  }
}

function insertionSort(arr, left, right) {
  for (let i = left + 1; i <= right; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

Frequently Asked Questions

About IntroSort (Introspective Sort)

What is IntroSort?

Why does IntroSort switch algorithms?

What is the time complexity of IntroSort?

Is IntroSort stable?

What triggers the switch to Heap Sort?

What triggers the switch to Insertion Sort?

What is the space complexity of IntroSort?

How does IntroSort compare to Tim Sort?

Is IntroSort an in-place sort?

Why is it called 'Introspective' Sort?

Where can I learn more?