0

While learning XQuery I'm trying to implement a merge sort.

For joining two already sorted sequences into one I wanted to implement a helper function called "merge".

It currently looks like this: 

declare function local:merge($seq1 as xs:integer*, $seq2 as xs:integer*) as xs:integer*{

if(empty($seq1) and empty($seq2)) then ()
else if(empty($seq1)) then $seq2
else if(empty($seq2)) then $seq1
else

let $zahl1 := $seq1[1]
let $zahl2 := $seq2[2]

return 
if($zahl1 < $zahl2) then ($zahl1, local:merge(fn:subsequence($seq1,2), $seq2))
else if($zahl2 < $zahl1) then ($zahl2, local:merge($seq1, fn:subsequence($seq2,2)))
else ($zahl1, $zahl2, local:merge(fn:subsequence($seq1,2), fn:subsequence($seq2,2)))

};

I'm testing my code with this call:

local:merge((1,3,6,9,10), (1,2,4,6,8,11))

Somehow the result isn't always correct (under this is the result for the call from above):

 1 2 3 4 6 6 8 9 10 8 11

The idea behind this was that I always check if the first number of a sequence is bigger or smaller than the one in the other sequence. I would then add the smaller number to my result, cut the sequence with the smaller number into a subsequence without the just added number and go again recursively.

The break condition are when either one of the two sequences is empty or both.

I can't see my mistake at the moment, perhaps it's something little that I'm overlooking.

Can you show me where I need to change my code that it works correct?

Thanks a lot for your help.

4

2 回答 2

1

You have a copy/paste error in line 9 of the function, let $zahl2 := $seq2[2] should be let $zahl2 := $seq2[1]. The rest of your function works correctly.

You can however omit the check if both arguments are empty, because the next one returns $seq2, which is empty, too:

  if(empty($seq1)) then $seq2
  else if(empty($seq2)) then $seq1
  else
    let $zahl1 := $seq1[1]
    ...
于 2013-03-30T17:07:47.413 回答
0

Of course a far easier way to sort it is:

for $i in $sequence order by $i return $i
于 2013-03-30T22:14:06.197 回答