home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2141 < prev    next >
Encoding:
Internet Message Format  |  1992-07-31  |  1.9 KB
  1. Path: sparky!uunet!mcsun!uknet!icdoc!sot-ecs!sra
  2. From: sra@ecs.soton.ac.uk (Stephen Adams)
  3. Newsgroups: comp.programming
  4. Subject: in-place merge
  5. Message-ID: <SRA.92Jul30223243@nansen.ecs.soton.ac.uk>
  6. Date: 30 Jul 92 21:32:43 GMT
  7. Sender: news@ecs.soton.ac.uk
  8. Organization: Southampton University Computer Science
  9. Lines: 57
  10. Nntp-Posting-Host: nansen
  11.  
  12. Does anyone know of an O(n) time and O(1) space algorithm
  13. for doing an in-place merge, or have a proof that it is not
  14. possible?
  15.  
  16. By an in-place merge I mean the following:
  17.  
  18. Given
  19.  
  20.   . an array a[1:n] of n elements
  21.   . k such that 1<=k<=n-1
  22.   . a[1:k] is sorted
  23.   . a[k+1:n] is sorted
  24.  
  25. I want to merge the two sorted lists a[1:k] and a[k+1:n],
  26. resulting in a single sorted list a[1:n], by re-arranging
  27. the elements of a (i.e. in-place).  You are allowed only to
  28. use a fixed amount of extra storage.
  29.  
  30. The only algorithms I know of for merging assume either a
  31. separate destination array, or pointers that link the
  32. elements together, as in linked lists.
  33.  
  34. I can think of an O(n^2) time algorthim:
  35.  
  36.     p := 1;    // `head' for first list
  37.     q := k+1;  // `head' of second list
  38.  
  39.     while q<n  do
  40.         if a[p] <= a[q] then
  41.         // a[p] is in the correct position
  42.         p := p+1
  43.         else
  44.         // must move all of the first list to make a
  45.                 // space for a[q]
  46.         for i:= q-1 downto p do  a[i] := a[i-1];
  47.         a[p] := a[q];
  48.         p:=p+1;
  49.         q:=q+1;
  50.         end if
  51.     end
  52.  
  53. This is clearly O(n^2): if k=n/2 and a[1]>a[k+1] then the
  54. lists end up by being swapped.  All of the first list is
  55. moved, one place at a time, to the position of the second
  56. list.  This is k moves of k words = n^2/4, assignments.
  57. Space is O(1) as we only use indexes p, q and i.
  58.  
  59.  
  60. I am prepared to relax the problem:
  61.  
  62.   . k is near, or exactly n/2
  63.   . O(log n) space
  64. --
  65. Stephen Adams                           Email: S.R.Adams@ecs.soton.ac.uk
  66. Electronics and Computer Science        Tel: 0703 593649
  67. University of Southampton               Fax: 0703 593045 
  68. Southampton  SO9 5NH,  UK
  69.