：问一道关于两数组排序的算法问题。

Question

两个子数组,A1[1..k],A2[k+1..n].A1,A2都已经从小到大排好序.要求把A1,A2合并成一个排好序的数组
要求:最坏情况下的时间复杂度为O(N)
辅助空间为O(1)  写出算法，或者用delphi实现。

Answer 1

我不知道我这种方法最坏情况下时间复杂度为多少，也不知辅助空间为多少。
我知道这个排序很简单。
procedure sort(var a1,a2,a3:array of integer);
var
i,j,n:integer;
begin
 i:=0;
 j:=0;
 for n:=low(a3) to high(a3) do
 begin
     if (i>high(a1)) and (j<=high(A2)) then
     begin
        A3[n]:=A2[j];
        j:=j+1;
        continue;
     end;     if (j>high(A2)) and (i<=high(A1)) then
     begin
       A3[n]:=A1[i];
       i:=i+1;
       continue;
     end;     if (i>high(A1)) and (j>high(A2)) then exit;
 case (A2[j]>=A1[i]) of
 true:begin
      A3[n]:=A1[i];
      i:=i+1;
      end;
 false:begin
       A3[n]:=A2[j];
       j:=j+1;
       end;
 end;
 end;
end;

Answer 2

有关归并算法的完整delphi实现，请参照Julian Bucknall的《delphi算法与数据结构》如果回答就是抄书了。就是Merge Sort。还可以参照短歌兄的用归并排序改进快速排序的那个帖子。在文档区：http://www.csdn.net/Develop/Read_Article.asp?Id=21786不要要答案，能自己找就自己找…… 我就不明白……毛爷爷告诉我们：自己动手，丰衣足食……

Answer 3

你们的什么属于我不懂，和和，反正我能够实现，但不知是否能满足要求了：TArray1D=Array of Double//首先写一个辅助程序：在数组的一个位置插入一个数
Function InsertinArray(Index:Integer;Value:Double;A:TArray1D):TArray1D;
Var
  i,Size:Integer;
Begin
   Size:=length(A);
   SetLength(Result,Size+1);
   For i:=0 to Index-1 do
     Result[i]:=A[i];
   Result[Index]:=Value;
   For i:=Index+1 to Size Do
     Result[i]:=A[i-1];
End;//然后进行排序和并
Procedure SortMerg(A1,A2:TArray1D);
Var
  i,j,k:Integer;
Begin
  k:=0; 
  For i:=Low(A2) to High(A2) do
  Begin
    j:=k;
    While (j<=High(A2))Do  
    Begin
       If j>0 then 
       Begin 
         If (A2[i]<=A1[j]) and A2[i]>A1[j-1]) Then 
         Begin
           k:=j;
           A1:=InsertinArray(j,A2[i],A1); //这里不知道对不对，可能需要一个辅助数组
           Break;
         End Else 
           Inc(j);
       End Else 
       Begin
         If A2[i]<A1[0] Then 
         Begin
           k:=0;
           A1:=InsertinArray(0,A2[i],A1); //这里不知道对不对，可能需要一个辅助数组
           Break;
         End Else 
           Inc(j);
       End;
    End;  //End While
  End; //End For
End;

Answer 4

上面第二个子程序可以写得简略一点
//然后进行排序和并
Procedure SortMerg(A1,A2:TArray1D);
Var
  i,j,k:Integer;
Begin
  k:=-1; 
  For i:=Low(A2) to High(A2) do
  Begin
    j:=k+1;
    While (j<=High(A2))Do  
    Begin
       If j>0 then 
       Begin 
         If (A2[i]<=A1[j]) and A2[i]>A1[j-1]) Then 
         Begin
           k:=j;
           Break;
         End Else 
           Inc(j);
       End Else 
       Begin
         If A2[i]<A1[0] Then 
         Begin
           k:=0;
           Break;
         End Else 
           Inc(j);
       End;
    End;  //End While
    A1:=InsertinArray(k,A2[i],A1); //这里不知道对不对，可能需要一个辅助数组
  End; //End For
End;

Answer 5

抱歉，各位，这道题目看似简单，其实是一道很难的题目。我同学在“水木清华”那的算法版贴了问题，也没有得到满足题目的解答。我已经把老师给出得题目都贴出来了。a1[1..k-1]和a2[k-1,n]是两个子数组，而且已经排序为从小到大，现在要把他们排序成a[1..n]（从小到大）。
  注意：不是只要能实现就可以了。这样的题目光实现的话，绝大多数人都能轻松做出来的。问题是在实现的时候还有条件：
  1、时间复杂度为O(n),
  2、辅助空间为O(1)。如果觉得这个题目说的不够详细，那就到这里了。再放两天我就结贴。