program written in dafny, implementing the Merge Sorted Arrays in-Place algorithm

Question

Here is the program that given to me in dafny:

method Main() {
    var a, b := new int[3] [3,5,8], new int[2] [4,7];
    print "Before merging the following two sorted arrays:\n";
    print a[..];
    print "\n";
    print b[..];
    ghost var AB := multiset(a[..]+b[..]);
    assert Sorted(a[..]) && Sorted(b[..]);
    MergeSortedArraysInPlace(a, b, AB);
    assert multiset(a[..]+b[..]) == AB;
    assert Sorted(a[..]+b[..]);
    print "\nAfter merging:\n";
    print a[..]; // [3,4,5]
    print "\n";
    print b[..]; // [7,8]
}

predicate Sorted(q: seq<int>)
{
    forall i,j :: 0 <= i <= j < |q| ==> q[i] <= q[j]
}

method MergeSortedArraysInPlace(a: array<int>, b: array<int>, ghost AB: multiset<int>)
    requires Sorted(a[..]) && Sorted(b[..])
    requires multiset(a[..]+b[..]) == AB
    requires a != b
    ensures Sorted(a[..]+b[..])
    ensures multiset(a[..]+b[..]) == AB
    modifies a, b

now i need to Implement iteratively, correctly, efficiently and clearly the MergeSortedArraysInPlace method. Restriction: Merge the arrays in place, using constant additional space only.

so the implementation that i wrote is the following:

method MergeSortedArraysInPlace(a: array<int>, b: array<int>, ghost AB: multiset<int>)
    requires Sorted(a[..]) && Sorted(b[..])
    requires multiset(a[..]+b[..]) == AB
    requires a != b
    ensures Sorted(a[..]+b[..])
    ensures multiset(a[..]+b[..]) == AB
    modifies a, b
{
    var i := 0;
    var j := 0;
    while (i < a.Length && j < b.Length)
    decreases a.Length - i, if i < a.Length then b.Length - j else 0 - 1
    {
         // if a[i] <= b[j] then both array is
        // already sorted
        if (a[i] <= b[j]) {
            i := i + 1;
        }
        // if a[i]>b[j] then first we swap
        // both element so that a[i] become
        // smaller means a[] become sorted then
        // we check that b[j] is smaller than all
        // other element in right side of b[j] if
        // b[] is not sorted then we linearly do
        // sorting means while adjacent element are
        // less than new b[j] we do sorting like
        // by changing position of element by
        // shifting one position toward left
         else if (a[i] > b[j]) {
            var t := a[i];
                a[i] := b[j];
                b[j] := t;
                i := i +1;
            if (j < b.Length - 1 && b[j + 1] < b[j]) {
             var temp := b[j];
             var tempj := j + 1;
                    while (tempj < b.Length && b[tempj] < temp)
                    decreases b.Length - tempj, if tempj < b.Length then temp - b[tempj] else 0 - 1
                     invariant   0 <= tempj < b.Length
                    {
                        b[tempj - 1] := b[tempj];
                        tempj := tempj+1;
                        if(tempj == b.Length){
                            break;
                        }
                    }
                    b[tempj - 1] := temp;
                }
         } 
    }
}

But for some reason I still get "A postcondition might not hold on this return path." on the following post conditions:

ensures Sorted(a[..]+b\[..])
ensures multiset(a[..]+b\[..]) == AB

I don't know what the problem could be, I would appreciate your help :)

Answer 1

If you need to sort each array in place, you can use an algorithm like Insertion Sort, which can sort an array in place with constant additional space.

Here is an implementation of Insertion Sort that sorts the given arrays a and b in place:

method SortInPlace(a: array<int>)
    modifies a
{
    var i := 1;
    while (i < a.Length)
        invariant 1 <= i <= a.Length
        decreases a.Length - i
    {
        var j := i;
        while (j > 0 && a[j - 1] > a[j])
            invariant 0 <= j < i
            decreases j
        {
            var temp := a[j];
            a[j] := a[j - 1];
            a[j - 1] := temp;
            j := j - 1;
        }
        i := i + 1;
    }
}

method Main() {
    var a := new int[3] [3,5,8];
    var b := new int[2] [4,7];

    print "Before sorting the following two arrays:\n";
    print a[..];
    print "\n";
    print b[..];

    SortInPlace(a);
    SortInPlace(b);

    print "\nAfter sorting in place:\n";
    print a[..];
    print "\n";
    print b[..];
}

In this implementation, the SortInPlace method takes an array a as input and sorts it in place using Insertion Sort. The Main method creates two arrays a and b, prints their contents, sorts them in place using SortInPlace, and then prints their contents again to verify that they are sorted.

Note that if you need to sort multiple arrays, you can simply call the SortInPlace method on each array.