gistfile1.dart

int N = 1000000;

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

  Stopwatch start = new Stopwatch();
  start.start();
  arr = mergeSort(arr);
  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;
}

List<int> merge (List<int> left, List<int> right) {
  int leftInc = 0, rightInc = 0, leftLength = left.length, rightLength = right.length;
  List<int> result = new List<int>();
  while (leftInc < leftLength || rightInc < rightLength) {
    if (leftInc < leftLength && rightInc < rightLength) {
      if (left[leftInc] < right[rightInc]) {
        result.add(left[leftInc++]);
      }
      else {
        result.add(right[rightInc++]);
      }
    }
    else if (leftInc < leftLength) {
      result.add(left[leftInc++]);
    }
    else {
      result.add(right[rightInc++]);
    }
  }
  return result;
}

List<int> mergeSort(List<int> arr) {
  if (arr.length === 1) {
    return arr;
  }
  int mid = (arr.length / 2).toInt();
  return merge(mergeSort(arr.getRange(0, mid)), mergeSort(arr.getRange(mid, arr.length - mid)));
}