A merge-sort implementation

gistfile1.rs

fn merge_sort<copy a>(&&d: [mutable a]) {
  fn merge<copy a>(&&data: [mutable a], &&temp: [mutable a], low: uint, middle: uint, high: uint) {
    let resultI = low;
    let tempI = low;
    let destI = middle;
    while tempI < middle && destI <= high {
      if data[destI] < temp[tempI] {
        data[resultI] = data[destI];
        resultI += 1u;
        destI += 1u;
      } else {
        data[resultI] = temp[tempI];
        resultI += 1u;
        tempI += 1u;
      }
    }
      
    while tempI < middle {
      data[resultI] = temp[tempI];
      resultI += 1u;
      tempI += 1u;
    }
  }

  fn merge_sort_recursive<copy a>(&&data: [mutable a], &&temp: [mutable a], low: uint, high: uint) {
    assert 0u <= low;
    assert low <= high;
    assert high < vec::len(data);

    let n = high - low + 1u;
    if n < 2u {
      ret; // section is already sorted.
    }

    let middle = low + n / 2u;
    let i = low;
    while i < middle {
      temp[i] = data[i];
      i += 1u;
    }
    merge_sort_recursive(temp, data, low, middle - 1u);
    merge_sort_recursive(data, temp, middle, high);

    merge(data, temp, low, middle, high);
  }

  let n = vec::len(d);
  if n < 2u {
    ret;
  }
  let tmp: [mutable a] = d;

  merge_sort_recursive(d, tmp, 0u, n - 1u); 
}