Merge Sort

Generic implementation flavours covering

• in-place (mutable) or out-of-place (immutable) sorting of a given array
• calculation of number of inversion occurred

In-place sorting (mutable)

The implementation re-orders/mutates the input array and returns the number if inversions occurred

In relation to time and space complexity, the implementation offers

• merging operations of O(n+m) swaps with no use of temp storage
• Takes up to O(n+m) * usize memory space per merge cycle which can be further reduced to O(n) * usize

pub trait MergeSort<T>
    where T : Ord {
    fn mergesort_mut<F>(&mut self, fn_merge: F ) -> usize
        where F: Copy + FnMut(&mut[T], &mut[T]) -> usize;
    fn mergesort(&self) -> (usize, Vec<T>);
}

impl<T>  MergeSort<T> for [T]
    where T: Copy + Clone + Ord {
    /// Sort function based on the merge sort algorithm
    /// Sorts the mutable vector with in-place operations
    /// while it returns the total count of inversions occurred
    ///
    /// The following functions are available to use as passing parameter
    /// - merge_mut : safe to use with non-adjacent; time: O(n+m), space: O(2n+m)*usize
    /// - merge_mut_adjacent : use only when slices are adjacent in memory: time: O(n+m), space: O(n)*usize
    ///
    /// ```
    /// use csx3::{ merge::Merge, sort::merge::MergeSort };
    ///
    /// let input = &mut [8, 4, 2, 1];
    ///
    /// assert_eq!( input.mergesort_mut(Merge::merge_mut_adjacent), 6 );
    /// assert_eq!( input, &[1,2,4,8] );
    /// ```
    fn mergesort_mut<F>(&mut self, mut fn_merge: F ) -> usize
        where F: Copy + FnMut(&mut[T], &mut[T]) -> usize  {

        let len = self.len();

        //println!("\tInput: ({}){:?} =>", len, v);
        match len {
            // unity slice, just return it
            0..=1 => 0,
            // sort the binary slice and exit
            // use a local variable to eliminate the need for &mut as input
            // and given we output a new vector
            2 => {
                if self[0] > self[1] {
                    self.swap(0, 1);
                    return 1usize
                }
                0usize
            },
            // if slice length longer than 2 then split recursively
            _ => {
                let (left, right) = self.split_at_mut(len >> 1);
                let left_inv = left.mergesort_mut(fn_merge);
                let right_inv = right.mergesort_mut(fn_merge);

                // merge the two slices taking an in-place merging approach - no additional memory
                // plus return the total inversions occured
                let merge_inv = fn_merge(left, right);

                //println!("\tMerged: {:?}{:?} => {}", left, right, left_inv + right_inv + merge_inv);
                left_inv + right_inv + merge_inv
            }
        }
    }

Out-of-place sorting (immutable)

The implementation returns a sorted copy of the input array along with the total number of inversions occurred.

The implementation

• Utilises Iterator traits of input slices to retrieve the next in order element through the next() function.
• Returns the inversion count per position and as part of calling next() function
• Takes O(n+m) * typeof(array) memory space per merge cycle

    /// Sort function based on the merge sort algorithm
    /// Returns a new sorted vector given an input reference slice - heap allocations
    /// along with the total count of inversions occurred
    /// ```
    /// use csx3::sort::merge::MergeSort;
    ///
    /// let input = &[8, 4, 2, 1];
    ///
    /// assert_eq!( input.mergesort(), (6, vec![1,2,4,8]) );
    /// ```
    fn mergesort(&self) -> (usize, Vec<T>) {

        let len = self.len();

        //println!("\tInput: ({}){:?} =>", len, v);
        match len {
            // unity slice, just return it
            0..=1 => (0, self.to_vec()),
            // sort the binary slice and exit
            // use a local variable to eliminate the need for &mut as input
            // and given we output a new vector
            2 => {
                let mut inv_count = 0usize;
                let mut output = self.to_vec();
                if self[0] > self[1] {
                    output.swap(0, 1);
                    inv_count += 1;
                }
                (inv_count, output)
            },
            // if slice length longer than 2 then split recursively
            _ => {
                let (left, right) = self.split_at(len >> 1);
                let (left_inv, left) = left.mergesort();
                let (right_inv, right) = right.mergesort();

                // return a vector of the merged but ordered slices
                // plus inversions vector; inversion count per position
                let (merge_vec, output ):( Vec<_>, Vec<T>) = MergeIterator::new(left.iter(),right.iter()).unzip();
                // println!("\tInversion Vector: {:?}", &merge_vec);

                // sum up the inversion count vector
                let merge_inv : usize = merge_vec.into_iter().filter(|x| *x > 0).sum();
                //println!("\tInversion Vector: {:?}", &merge_vec);

                //println!("\tMerged: {:?}{:?} => {}", left, right, left_inv + right_inv + merge_inv);
                (left_inv + right_inv + merge_inv, output)
            }
        }
    }