Quick Sort
- Mutable sorting of input array using randomised pivot for partitioning
Merge Sort
Versions
- Immutable sorting returning a sorted copy of the input
- Performance: O(n log n)
- Memory: O(n log n) * heap alloc/dealloc sizeof(n)
- Mutable sorting with in-place merge operations
- Overall Performance: O(n log n) with intelligent swapping
- Approach to in-place merge operations,
- Merge memory adjacent sub-arrays :
fn merge_mut_adjacent()- Use of intelligent swaps
- Performance: O(n+m),
- Memory impact: O(n) * usize
- Merge Non-adjacent sub-arrays :
fn merge_mut()- Use of intelligent Swaps
- Performance: O(n+m)
- Memory: O(2n+m) * usize
- Merge memory adjacent sub-arrays :
In-place Merge Algorithm with intelligent swapping
General Approach
In an “In place” merge of two ordered arrays it is always required to maintain a pivot between merged and unmerged sub-arrays as we go over the process of
- Use comparison indexes
(c,j)to find the smallest element between (a) the left and (b) right ordered arrays - Swap the next smallest element of the left and right sub-arrays against a pivot position
(p) - Repeat until we’ve exhausted comparing and swapping all elements
Challenge
Taking a naive first step
By trying to swap the smallest element of the two arrays with the pivot we quickly realise that things are getting out of control very soon. For example,
p and equal to [1,2] while the unmerged region is [(5!!,3),(4,6)] which is clearly out-of-order and the result from then on is unpredictable. During the 2nd iteration, the left comparison index [c] points to a 2 rather 3 which is now at the 4th position in the right array, or the 2nd position in the unmerged partition.Therefore, we need to find a way to maintain a solid comparison index reference
[c] for the left array while we iterate through
Problem Solution
Canceling the Rotation during right swaps
It becomes obvious that during the right swap operation our left array is rotated left as seen below
c j p [c] > [j] Action
c/p j ======= ========= ========================
[(1 , 3 , 5)] [(2 , 4 , 6)] 1 1 1 1 2 left swap(c,p) incr(c,p)
c/p j
[ 1 ,(3 , 5)] [(2 , 4 , 6)] 2 1 2 3 2 right swap(j,p) incr(j,p)
c p j
[ 1 , 2 ,(5 ] [ 3),(4 , 6)] <-- Here instead of [3,5] we have [5,3]
Moreover, the partition point [p] more or less points to the where the left comparison index [c] should have been, that is, the unmerged partition. Let's try this time with
- reverting the rotation effect after each right swap hence bringing the left unmerged part back to order
- using
[c]as both the partition and the left comparison index
c j [c] > [j] Action
c j ==== ========= ============================
[(1 , 3 , 5)] [(2 , 4 , 6)] 1 1 1 2 No swap, just incr(c)
c j
[ 1 ,(3 , 5)] [(2 , 4 , 6)] 2 1 3 2 right swap(j,c), incr(c,j)
c j
[ 1 , 2 ,(5 ] [ 3),(4 , 6)] 3 2 rotate right by 1, from c to j excluded
c j
[ 1 , 2 ,(3 ] [ 5),(4 , 6)] 3 2 3 4 No swap, just incr(c)
c j
[ 1 , 2 , 3 ] [(5),(4 , 6)] 4 2 5 4 right swap(j,c), incr(c,j)
c j
[ 1 , 2 , 3 ] [ 4 ,(5),(6)] 5 3 rotate right by 1, from c to j excluded
c j
[ 1 , 2 , 3 ] [ 4 ,(5),(6)] 5 3 5 6 No swap, just incr(c)
c/j
[ 1 , 2 , 3 ] [ 4 , 5 ,(6)] 6 3 c == j (!) nothing more to compare... we've finished !!
Nice! It works, but only on paper. Although we overcame the conflict between pivot [p] and left comparison index [c] the obvious issues here is that our indexing across the two arrays is broken. Definitely 6 == 3 isn't correct, because [c] has to operate in both arrays while [j] operates solely in the right array.
However, we do know that mergesort, performs merge on memory adjacent array segments hence this can be mitigated by reconstructing the parent array out of the two fragments so that, working array = *left_array[0] .. *left_array[0] + (left_array.len() + right_array.len())
Left Array Right Array
+---+---+---+ +---+---+---+
| 2 | 4 | 6 | | 1 | 3 | 5 | Adjacent array segments
+---+---+---+ +---+---+---+
| | | | | |
+---+---+---+---+---+---+
|&2 |&4 |&6 |&1 |&3 |&5 | Memory reconstructed and operated as a continuous array i.e.
+---+---+---+---+---+---+ we recast a slice with start pointer left_array[0]
c j and length = left (len + right len)*sizeof()
Let's repeat the example but through the memory reconstructed array.
