Interleave two sorted arrays

Question

To learn Rust, I tried to write a function that takes two sorted arrays of integers and interleaves them into one longer sorted array.

Is this approach ok? Have I made any mistakes?

fn main() {
 let a = [1, 3, 4, 4];
 let b = [0, 2, 5, 6];
 println!("{:?}", merge(&a, &b));
}
fn merge(list_a : &[i32; 4], list_b : &[i32; 4]) -> [i32; 8] {
 let mut merged_list: [i32; 8] = [0; 8];
 let mut idx = 0;
 let mut idx_b = 0;
 for a in list_a.iter() {
 while idx_b < list_b.len() && list_b[idx_b] < *a {
 merged_list[idx] = list_b[idx_b];
 idx_b +=1;
 idx += 1;
 }
 merged_list[idx] = *a;
 idx += 1;
 }
 for b in list_b[idx_b..].iter() {
 merged_list[idx] = *b;
 idx += 1;
 }
 println!("{:?}", merged_list);
 merged_list
}
#[cfg(test)]
mod tests {
 use super::*;
 #[test]
 fn test_merge() {
 let a = [1, 3, 3, 7];
 let b = [0, 4, 6, 8];
 assert_eq!(merge(&a, &b), [0, 1, 3, 3, 4, 6, 7, 8]);
 }
}

Answer 1

Your code is quite reasonable. I'm happy to see that you included both a main function and tests, which make it easy to see that the function works.

1. Stylistically, colons (:) are "attached" to the argument name, they don't have a space on both sides:

   -fn merge(list_a : &[i32; 4], list_b : &[i32; 4]) -> [i32; 8] {
   +fn merge(list_a: &[i32; 4], list_b: &[i32; 4]) -> [i32; 8] {
   

2. You should let type inference do its thing; there's no need to provide the type for merged_list:

   let mut merged_list = [0; 8];
   

3. Instead of calling .iter(), it's customary to just pass a reference to an array / slice / Vec to the for loop:

   for a in list_a { /* ... */ }
   for b in &list_b[idx_b..] { /* ... */ }
   

Looking beyond the current implementation, you'll find that arrays, which have a fixed-size, are usually pretty limiting, at least until RFC 2000 is implemented.

Until then, it's common to either use a macro to implement a trait for many concrete types, or to take a slice (&[T]) and return a Vec<T>. The macro route is visible in the standard library and is why many array implementations only go up to 32 elements.

I'd encourage you to write a version that takes two slices, returns a Vec, and uses a match statement inside a loop; I think such a merge sort is a nice showcase of some of Rust's abilities. In such a solution, you should not need to use any indexing operations!

Answer 2

I can't see any obvious glaring bugs, but I can make a few suggestions to improve your initial baby steps, namely

Varying length arrays

Take your learning a step further and make the functions take arrays of varying lengths and see if your implementation still works. From the looks of it, it should still work without being heavily modified.

Generic array

I am not too familiar with Rust, but if it supports generics, then why don't you make the function generic so that it can take any two arrays of the same data type and merge them.

Conclusion

That is all. The code didn't really have a lot of ways things can go wrong because of the fixed size of the arrays. But you did a good job with the merge function which is what I think you were going for in the first place. See if you can implement the two suggestions above, then create another post

• Moberg: That's actually what I tried. But i didn't manage to get it to compile, the return type was tricky. (i asked about it, but it was edited away, wrong forum i guess ^^) I'll give it another try, maybe ask on SO.
• smac89: Ok yea you should ask it on SO. I honestly can't say I agree with such practice as deleting only part of someone's question and leaving the rest, I believe this infringes some rule/policy on this site. If the author is not allowed to modify their code to include more details and such, I don't see why it may be allowed for someone else
• Shepmaster: @Moberg it's because that part of the question (asking how to do something) is off-topic for Code Review, as the revision log mentions.
• Shepmaster: @smac89 If the author is not allowed to modify their code to include more details and such — the author is very much encouraged to add more details that are relevant to the code review; why do you think otherwise? The author is not allowed to change the question being asked in many cases or to ask how to do something that they are unable to.
• smac89: @Shepmaster, then it should have been flagged as off-topic rather than editing it to remove parts of the question. As it turns out, the part someone removed is what I unknowingly suggested.

Answer 3

I'm rather new to Rust myself and must admit the indexless function Shepmaster alludes to is not obvious. If it does occur to me I'll post again.

smac89 and Shepmaster covered everything but didn't post any code.

My solution (just the function) is as follows:

pub fn merge(s1: &[i32], s2: &[i32]) -> Vec<i32> {
 let mut merged = Vec::<i32>::new();
 let (end1, end2) = (s1.len(), s2.len());
 let (mut i1, mut i2) = (0usize, 0usize);
 while i1 < end1 && i2 < end2 {
 let (x1, x2) = (s1[i1], s2[i2]);
 merged.push( if x1 < x2 { i1+=1; x1 } else { i2+=1; x2 } );
 }
 merged.extend( if i1 < end1 { &s1[i1..] } else { &s2[i2..] } );
 merged
}

Assignment via tuples is nice for related variables but at some point is gets too crowded and hard to read. You could expand it out if you like.

For a short function like this I see no harm in abbreviated variable names. I used mostly two-character names here, but would never do that were more variables in use.

• Shepmaster: the indexless function Shepmaster alludes to is not obvious — A quickly thrown together example
• wlciii: Good example but I've a question. You encouraged writing it as an exercise or because it's better in some way? It seems a legitimate, equally good alternative but not an improvement. BTW, I worked on it before you posted and it was a good exercise.