gistfile1.dart

int N = 1000000;

void main() {
  List<int> arr = initArray();

  Stopwatch start = new Stopwatch();
  start.start();
  merge_sort(arr, 0, N);
  start.stop();
  print(start.elapsedInMs());

  bool correct = verifyArr(arr);
  print("Correct ? $correct");
}

bool verifyArr(List<int> arr) {
  int i = 0;
  for (i = 0; i < N; i++) {
      if (arr[i] !== i+1) {
          return false;
      }
  }
  return true;
}

List<int> initArray() {
    List<int> arr = new List(N);
    int i = 0;
    
    for (i = 0; i < N; ++i) {
        arr[i] = N - i;
    }
    return arr;
}

void hot_merge(List<int> arr, int p, int r, List L, List R) {
    int i = 0, j = 0, k = 0, Llen = L.length, Rlen = R.length;
    for (k = p; k < r; k++) {
        if (j >= Rlen) {
            arr[k] = L[i++];
        } else if (i >= Llen) {
            arr[k] = R[j++];
        } else {
            if (L[i] <= R[j]) {
                arr[k] = L[i++];
            } else {
                arr[k] = R[j++];
            }
        }
    }
}

void merge(List<int> arr, int p, int q, int r) {
    List<int> L = arr.getRange(p, q - p);
    List<int> R = arr.getRange(q, r - q);
    hot_merge(arr, p, r, L, R);
}

void merge_sort(arr, p, r) {
    int q = 0;
    if ((r - p) > 1) {
        q = ((p + r)/2).toInt();
        merge_sort(arr, p, q);
        merge_sort(arr, q, r);
        merge(arr, p, q, r);
    }
}