Skip to content

Instantly share code, notes, and snippets.

@creativcoder
Last active November 5, 2023 13:23
Show Gist options
  • Save creativcoder/20fda0f1a947bf2af3b93ab394d6bacb to your computer and use it in GitHub Desktop.
Save creativcoder/20fda0f1a947bf2af3b93ab394d6bacb to your computer and use it in GitHub Desktop.
Merge k sorted arrays in Rust
// Blog post: https://creativcoder.dev/merge-k-sorted-arrays-rust
// Merge 2 sorted arrays
fn merge_2(a: &[i32], b: &[i32]) -> Vec<i32> {
let (mut i, mut j) = (0, 0);
let mut sorted = vec![];
let remaining;
let remaining_idx;
loop {
if a[i] < b[j] {
sorted.push(a[i]);
i += 1;
if i == a.len() {remaining = b; remaining_idx = j; break;}
} else {
sorted.push(b[j]);
j += 1;
if j == b.len() {remaining = a; remaining_idx = i; break;}
}
}
for i in remaining_idx..remaining.len() {
sorted.push(remaining[i]);
}
sorted
}
// Merge k sorted arrays
#[derive(Debug, Eq)]
struct Item<'a> {
arr: &'a Vec<i32>,
idx: usize
}
impl<'a> PartialEq for Item<'a> {
fn eq(&self, other: &Self) -> bool {
self.get_item() == other.get_item()
}
}
impl<'a> PartialOrd for Item<'a> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
self.get_item().partial_cmp(&other.get_item())
}
}
impl<'a> Ord for Item<'a> {
fn cmp(&self, other: &Self) -> Ordering {
self.get_item().cmp(&other.get_item())
}
}
impl<'a> Item<'a> {
fn new(arr: &'a Vec<i32>, idx: usize) -> Self {
Self {
arr,
idx
}
}
fn get_item(&self) -> i32 {
self.arr[self.idx]
}
}
use std::collections::BinaryHeap;
use std::cmp::Reverse;
use std::cmp::Ordering;
fn merge(arrays: Vec<Vec<i32>>) -> Vec<i32> {
let mut sorted = vec![];
let mut heap = BinaryHeap::with_capacity(arrays.len());
for arr in &arrays {
let item = Item::new(arr, 0);
heap.push(Reverse(item));
}
while !heap.is_empty() {
let mut it = heap.pop().unwrap();
sorted.push(it.0.get_item());
it.0.idx += 1;
if it.0.idx < it.0.arr.len() {
heap.push(it)
}
}
sorted
}
fn main() {
let a = vec![1, 5, 7];
let b = vec![-2, 3, 4];
let v = vec![a, b];
dbg!(merge(v));
}
@Valodim
Copy link

Valodim commented Jul 20, 2021

Would you care to state a license for this code? I would welcome MIT 👌

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment