import 'dart:math';

import 'package:test/expect.dart';

import 'package:test/scaffolding.dart';

const int RUN = 32;

void insertionSort(List list, int left, int right) {

for (int i = left + 1; i <= right; i++) {

int temp = list[i];

int j = i - 1;

while (j >= left && list[j] > temp) {

list[j + 1] = list[j];

j--;

}

list[j + 1] = temp;

}

}

void merge(List list, int left, int middle, int right) {

int length1 = middle - left + 1, length2 = right - middle;

List leftList = List.filled(length1, null),

rightList = new List.filled(length2, null);

for (int i = 0; i < length1; i++) {

leftList[i] = list[left + i];

}

for (int i = 0; i < length2; i++) {

rightList[i] = list[middle + 1 + i];

}

int i = 0, j = 0, k = 0;

while (i < length1 && j < length2) {

if (leftList[i] <= rightList[j]) {

list[k] = leftList[i];

i++;

} else {

list[k] = rightList[j];

j++;

}

k++;

}

while (i < length1) {

list[k] = leftList[i];

i++;

k++;

}

while (j < length2) {

list[k] = rightList[j];

k++;

j++;

}

}

void timSort(List list, int n) {

for (int i = 0; i < n; i += RUN) {

insertionSort(list, i, min((i + 31), n - 1));

}

for (int size = RUN; size < n; size = 2 * size) {

for (int left = 0; left < n; left += 2 * size) {

int middle = left + size - 1;

int right = min((left + 2 * size - 1), (n - 1));

merge(list, left, middle, right);

}

}

}

void main() {

test('test case 1', () {

List arr = [12, 213, 45, 9, 107];

timSort(arr, arr.length);

expect(arr, [9, 12, 45, 107, 213]);

});

test('test case 2', () {

List arr = [];

timSort(arr, arr.length);

expect(arr, []);

});

test('test case 3', () {

List arr = [-1, 0, 1];

timSort(arr, arr.length);

expect(arr, [-1, 0, 1]);

});

}