0. #lang racket
1.  
2. (define len vector-length)
3. (define ref vector-ref)
4.  
5. ; (kth k a b)
6. ;   Return the k'th largest value of the values in the two sorted vectors a and b.
7. (define (kth k a b)
8.   ; We have a loop in which we look for the kth element in the two subvectors
9.   ; of a and b given by the indices ai to aj and ai to bj.
10.   ; More preceisely:
11.   ; the indices ai and aj are the indices of the beginning and end (exclusive) of a subvector of a.
12.   ;     If d=1,  then the indices are ai, ai+1, ..., aj-1.
13.   ;     If d=-1, then the indices are aj+1, aj+1, ..., ai.
14.   ; That is, if d= 1 we are looking for the kth smallest element,
15.   ; and      if d=-1 we are looking for the kth greatest element.
16.  
17.   (let loop ([ai 0] [aj (len a)] ; search all of a
18.              [bi 0] [bj (len b)] ; search all of b
19.              [d 1] [k k])        ; look for kth smallest element
20.     ; Let's give names to the following useful expressions.
21.     (define m        (* d (- aj ai)))       ; length of the a subvector
22.     (define n        (* d (- bj bi)))       ; length of the b subvector
23.     (define a-empty? (= m 0))               ; is a empty?
24.     (define b-empty? (= n 0))               ; is b empty?
25.     (define ak       (quotient (+ m 1) 2))  ; index of middle element
26.     (define bk       (quotient (+ n 1) 2))  ; index of middle element
27.     ; The ith element from left or right according to d.
28.     (define (aref i) (ref a (+ ai (* d i))))
29.     (define (bref i) (ref b (+ bi (* d i))))
30.  
31.     (cond
32.       [a-empty?  (bref k)]     ; a is empty, so the kth element is in b
33.       [b-empty?  (aref k)]     ; b is empty, so the kth element is in a
34.       [(= k 0)   (if (= d 1)   ; we have found our element!
35.                      (min (aref k) (bref k))
36.                      (max (aref k) (bref k)))]
37.       [(and (< k (/ (+ m n) 2)) (> d 0))
38.        ; This means the sought after element is in the "right" half.
39.        ; So we flip the direction of both a and b.
40.        (loop (- aj d) (- ai d)
41.              (- bj d) (- bi d)
42.              (- d)
43.              (- (+ m n) (+ k 1)))]
44.       ; Now we are sure that the sought after element is in the "left" half.
45.       ; We compare the middle elements of a and b
46.       [(< (* d (aref (- ak 1)))
47.           (* d (bref (- bk 1))))
48.        ; The middle element of a is smaller/larger than the middle element of b,
49.        ; so we can rule out the ka elements in the first half of a.
50.        (loop (+ ai (* d ak)) aj
51.              bi              bj
52.              d  (- k ak))]
53.       [else
54.        ; otherwise we can rule out the kb elements in the first half of b.
55.        (loop ai              aj
56.              (+ bi (* d bk)) bj
57.              d  (- k bk))])))
58.  
59.  
60. (define (median a b)
61.   (define n   (+ (len a) (len b)))
62.   (define n/2 (quotient n 2))
63.   (if (odd? n)
64.       (kth n/2 a b)
65.       (* 1/2 (+ (kth (- n/2 1) a b)
66.                 (kth    n/2    a b)))))
67.  
68.  
69.  
70. (= (kth 0 #(1) #())  1)
71. (= (kth 0 #()  #(2)) 2)
72.  
73. (= (kth 0 #(1) #(2)) 1)
74. (= (kth 1 #(1) #(2)) 2)
75.  
76. (= (kth 0 #(1 2) #(3)) 1)
77. (= (kth 1 #(1 2) #(3)) 2)
78. (= (kth 2 #(1 2) #(3)) 3)
79.  
80. (= (kth 0 #(1) #(2 3)) 1)
81. (= (kth 1 #(1) #(2 3)) 2)
82. (= (kth 2 #(1) #(2 3)) 3)
83.  
84. (= (kth 0 #(1 2) #(3 4)) 1)
85. (= (kth 1 #(1 2) #(3 4)) 2)
86. (= (kth 2 #(1 2) #(3 4)) 3)
87. (= (kth 3 #(1 2) #(3 4)) 4)
88.  
89. (= (kth 0 #(1) #(2 3 4)) 1)
90. (= (kth 1 #(1) #(2 3 4)) 2)
91. (= (kth 2 #(1) #(2 3 4)) 3)
92. (= (kth 3 #(1) #(2 3 4)) 4)
93.  
94. (= (kth 0 #() #(1 2 3 4)) 1)
95. (= (kth 1 #() #(1 2 3 4)) 2)
96. (= (kth 2 #() #(1 2 3 4)) 3)
97. (= (kth 3 #() #(1 2 3 4)) 4)
98.  
99. (= (kth 0 #(1 2) #(3 4 5)) 1)
100. (= (kth 1 #(1 2) #(3 4 5)) 2)
101. (= (kth 2 #(1 2) #(3 4 5)) 3)
102. (= (kth 3 #(1 2) #(3 4 5)) 4)
103. (= (kth 4 #(1 2) #(3 4 5)) 5)
104.  
105. (= (kth 0 #(1 2 3) #(4 5)) 1)
106. (= (kth 1 #(1 2 3) #(4 5)) 2)
107. (= (kth 2 #(1 2 3) #(4 5)) 3)
108. (= (kth 3 #(1 2 3) #(4 5)) 4)
109. (= (kth 4 #(1 2 3) #(4 5)) 5)
110.  
111. (= (median #(1 2 3) #(4 5))   3)
112. (= (median #(1 2)   #(3 4 5)) 3)
113. (= (median #(1 2 3) #(4 5 6)) 3.5)

=>

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t

#t