Pure Programmer
Blue Matrix

Cluster Map

Project: Merge Sort

The [[Merge sort]] is very efficient sort that was first introduced by [[John von Neumann]] in 1945. It can be implemented very easily using recursion. Write a function that takes a list of integers and sorts the list without modifying it, returning a sorted list, using a merge sort. Test the function by creating a random list of integers, print the random list, sort the list, then print out the sorted list. Accept the number of integers to put in the list and the maximum integer to randomly generate on the command line. What is the worst case performance of the Merge sort?

Output
$ rustc MergeSort.rs error[E0425]: cannot find value `args` in this scope --> MergeSort.rs:75:5 | 75 | if args.len() != 3 { | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::env::args; | error[E0425]: cannot find function `exit` in this scope --> MergeSort.rs:77:3 | 77 | exit(1); | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::process::exit; | error[E0425]: cannot find value `Utils` in this scope --> MergeSort.rs:79:23 | 79 | let listSize:isize = Utils.stoiWithDefault(args[1], 10); | ^^^^^ not found in this scope error[E0425]: cannot find value `args` in this scope --> MergeSort.rs:79:45 | 79 | let listSize:isize = Utils.stoiWithDefault(args[1], 10); | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::env::args; | error[E0425]: cannot find value `Utils` in this scope --> MergeSort.rs:80:21 | 80 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100); | ^^^^^ not found in this scope error[E0425]: cannot find value `args` in this scope --> MergeSort.rs:80:43 | 80 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100); | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::env::args; | error[E0308]: mismatched types --> MergeSort.rs:13:23 | 13 | let leftSize:isize = left.len(); | ----- ^^^^^^^^^^ expected `isize`, found `usize` | | | expected due to this | help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit | 13 | let leftSize:isize = left.len().try_into().unwrap(); | ++++++++++++++++++++ error[E0308]: mismatched types --> MergeSort.rs:14:24 | 14 | let rightSize:isize = right.len(); | ----- ^^^^^^^^^^^ expected `isize`, found `usize` | | | expected due to this | help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit | 14 | let rightSize:isize = right.len().try_into().unwrap(); | ++++++++++++++++++++ error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:17:11 | 17 | if left[leftPtr] <= right[rightPtr] { | ^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:17:29 | 17 | if left[leftPtr] <= right[rightPtr] { | ^^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:18:21 | 18 | result.push(left[leftPtr]); | ^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:21:22 | 21 | result.push(right[rightPtr]); | ^^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:29:20 | 29 | result.push(left[leftPtr]); | ^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:33:21 | 33 | result.push(right[rightPtr]); | ^^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0308]: mismatched types --> MergeSort.rs:40:23 | 40 | let listSize:isize = list.len(); | ----- ^^^^^^^^^^ expected `isize`, found `usize` | | | expected due to this | help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit | 40 | let listSize:isize = list.len().try_into().unwrap(); | ++++++++++++++++++++ error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:57:20 | 57 | left.push(list[i]); | ^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:59:21 | 59 | right.push(list[i]); | ^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0425]: cannot find function `irandom` in this scope --> MergeSort.rs:87:20 | 87 | listToSort.push(irandom(maxInt)); | ^^^^^^^ not found in this scope error: aborting due to 18 previous errors Some errors have detailed explanations: E0277, E0308, E0425. For more information about an error, try `rustc --explain E0277`. $ rustc MergeSort.rs error[E0425]: cannot find value `args` in this scope --> MergeSort.rs:75:5 | 75 | if args.len() != 3 { | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::env::args; | error[E0425]: cannot find function `exit` in this scope --> MergeSort.rs:77:3 | 77 | exit(1); | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::process::exit; | error[E0425]: cannot find value `Utils` in this scope --> MergeSort.rs:79:23 | 79 | let listSize:isize = Utils.stoiWithDefault(args[1], 10); | ^^^^^ not found in this scope error[E0425]: cannot find value `args` in this scope --> MergeSort.rs:79:45 | 79 | let listSize:isize = Utils.stoiWithDefault(args[1], 10); | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::env::args; | error[E0425]: cannot find value `Utils` in this scope --> MergeSort.rs:80:21 | 80 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100); | ^^^^^ not found in this scope error[E0425]: cannot find value `args` in this scope --> MergeSort.rs:80:43 | 80 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100); | ^^^^ not found in this scope | help: consider importing this function | 7 + use std::env::args; | error[E0308]: mismatched types --> MergeSort.rs:13:23 | 13 | let leftSize:isize = left.len(); | ----- ^^^^^^^^^^ expected `isize`, found `usize` | | | expected due to this | help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit | 13 | let leftSize:isize = left.len().try_into().unwrap(); | ++++++++++++++++++++ error[E0308]: mismatched types --> MergeSort.rs:14:24 | 14 | let rightSize:isize = right.len(); | ----- ^^^^^^^^^^^ expected `isize`, found `usize` | | | expected due to this | help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit | 14 | let rightSize:isize = right.len().try_into().unwrap(); | ++++++++++++++++++++ error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:17:11 | 17 | if left[leftPtr] <= right[rightPtr] { | ^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:17:29 | 17 | if left[leftPtr] <= right[rightPtr] { | ^^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:18:21 | 18 | result.push(left[leftPtr]); | ^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:21:22 | 21 | result.push(right[rightPtr]); | ^^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:29:20 | 29 | result.push(left[leftPtr]); | ^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:33:21 | 33 | result.push(right[rightPtr]); | ^^^^^^^^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0308]: mismatched types --> MergeSort.rs:40:23 | 40 | let listSize:isize = list.len(); | ----- ^^^^^^^^^^ expected `isize`, found `usize` | | | expected due to this | help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit | 40 | let listSize:isize = list.len().try_into().unwrap(); | ++++++++++++++++++++ error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:57:20 | 57 | left.push(list[i]); | ^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0277]: the type `[isize]` cannot be indexed by `isize` --> MergeSort.rs:59:21 | 59 | right.push(list[i]); | ^ slice indices are of type `usize` or ranges of `usize` | = help: the trait `SliceIndex<[isize]>` is not implemented for `isize` = help: the trait `SliceIndex<[T]>` is implemented for `usize` = note: required for `Vec<isize>` to implement `Index<isize>` error[E0425]: cannot find function `irandom` in this scope --> MergeSort.rs:87:20 | 87 | listToSort.push(irandom(maxInt)); | ^^^^^^^ not found in this scope error: aborting due to 18 previous errors Some errors have detailed explanations: E0277, E0308, E0425. For more information about an error, try `rustc --explain E0277`.

Solution