abstract class Sorter {
  void sort(List<Comparable> input);
}

class BubbleSort extends Sorter {
  @override
  void sort(List<Comparable> input) {
    var n = input.length;
    var swapped = false;
    do {
      swapped = false;
      var newn = n;
      for (var i = 1; i < n; i++) {
        if (input[i].compareTo(input[i - 1]).isNegative) {
          swap(input, i - 1, i);
          swapped = true;
          newn = i;
        }
      }
      n = newn;
    } while(swapped);
  }
}

class MergeSort extends Sorter {
  @override
  void sort(List<Comparable> input) {
    var list = mergeSort(input);
    input.replaceRange(0, input.length, list);
  }

  List<Comparable> mergeSort(List<Comparable> input) {
    if (input.length <= 1) {
      return input;
    }

    var middle = (input.length / 2).toInt();

    var left = input.take(middle).toList();
    var right = input.skip(middle).toList();
    left = mergeSort(left);
    right = mergeSort(right);

    return merge(left, right);
  }

  List<Comparable> merge(List<Comparable> left, List<Comparable> right) {
    var list = [];

    while (left.isNotEmpty && right.isNotEmpty) {
      if (left.first.compareTo(right.first).isNegative) {
        list.add(left.first);
        left = left.skip(1).toList();
      } else {
        list.add(right.first);
        right = right.skip(1).toList();
      }
    }

    while (left.isNotEmpty) {
      list.add(left.first);
      left = left.skip(1).toList();
    }

    while (right.isNotEmpty) {
      list.add(right.first);
      right = right.skip(1).toList();
    }

    return list;
  }
}

class BogoSort extends Sorter {
  @override
  void sort(List<Comparable> input) {
    bool isSorted() {
      var sorted = true;
      for (var i = 1; i < input.length; i++) {
        if (input[i].compareTo(input[i - 1]).isNegative) {
          sorted = false;
        }
      }
      return sorted;
    }

    while (!isSorted()) {
      input.shuffle();
    }
  }
}

void swap(List input, int a, int b) {
  var tmp = input[a];
  input[a] = input[b];
  input[b] = tmp;
}

void main() {
  test([8, 4, 1, 4, 9, 1, 9, 19, 48, 10, 48, 672, 4719, 9, 0]);
  test(["B", "C", "T", "A", "R", "Z", "Y", "Q", "M", "G"]);
}

void test(List data) {
  print("Input: ${data}");
  testSorter(data, "Bubble Sort", new BubbleSort());
  testSorter(data, "Merge Sort", new MergeSort());
  //testSorter(data, "BOGO Sort", new BogoSort());
}

void testSorter(List data, String name, Sorter sorter) {
  data = new List.from(data);
  sorter.sort(data);
  print("${name}: ${data}");
}