CS3343/3341
 Analysis of Algorithms 
Spring 2012
  Median Examples   

Median of an Array in Sorted Order
     |                                  ^
   0 |    0    1    2    3    4    5    6    7    8    9   10   11   12 
-----|------------------------------------------------------------------
     |   10   11   12   13   14   15   16   17   18   19   20   21   22 
     |
     |   10   11   12   13   14   15   16   17   18   19   20   21   22 
     |
     |   10   11   12   13   14   15   16   17   18   19   20   21  (22)
     |
     |   10   11   12   13   14   15   16   17   18   19   20   21  (22)
     |
     |   10   11   12   13   14   15   16   17   18   19   20  (21) (22)
     |
     |   10   11   12   13   14   15   16   17   18   19   20  (21) (22)
     |
     |   10   11   12   13   14   15   16   17   18   19  (20) (21) (22)
     |
     |   10   11   12   13   14   15   16   17   18   19  (20) (21) (22)
     |
     |   10   11   12   13   14   15   16   17   18  (19) (20) (21) (22)
     |
     |   10   11   12   13   14   15   16   17   18  (19) (20) (21) (22)
     |
     |   10   11   12   13   14   15   16   17  (18) (19) (20) (21) (22)
     |
     |   10   11   12   13   14   15   16   17  (18) (19) (20) (21) (22)
     |
     |   10   11   12   13   14   15   16  (17) (18) (19) (20) (21) (22)
     |
     |   10   11   12   13   14   15   16  (17) (18) (19) (20) (21) (22))
     |
 MEDIAN: A[6] = 16

Median of an Array in Reverse Sorted Order
     |                                  ^
   0 |    0    1    2    3    4    5    6    7    8    9   10   11   12 
-----|------------------------------------------------------------------
     |   22   21   20   19   18   17   16   15   14   13   12   11   10 
     |
     |   10   21   20   19   18   17   16   15   14   13   12   11   22 
     |
     |  (10)  21   20   19   18   17   16   15   14   13   12   11   22 
     |
     |  (10)  21   20   19   18   17   16   15   14   13   12   11   22 
     |
     |  (10)  21   20   19   18   17   16   15   14   13   12   11  (22)
     |
     |  (10)  11   20   19   18   17   16   15   14   13   12   21  (22)
     |
     |  (10) (11)  20   19   18   17   16   15   14   13   12   21  (22)
     |
     |  (10) (11)  20   19   18   17   16   15   14   13   12   21  (22)
     |
     |  (10) (11)  20   19   18   17   16   15   14   13   12  (21) (22)
     |
     |  (10) (11)  12   19   18   17   16   15   14   13   20  (21) (22)
     |
     |  (10) (11) (12)  19   18   17   16   15   14   13   20  (21) (22)
     |
     |  (10) (11) (12)  19   18   17   16   15   14   13   20  (21) (22)
     |
     |  (10) (11) (12)  19   18   17   16   15   14   13  (20) (21) (22)
     |
     |  (10) (11) (12)  13   18   17   16   15   14   19  (20) (21) (22)
     |
     |  (10) (11) (12) (13)  18   17   16   15   14   19  (20) (21) (22)
     |
     |  (10) (11) (12) (13)  18   17   16   15   14   19  (20) (21) (22)
     |
     |  (10) (11) (12) (13)  18   17   16   15   14  (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13)  14   17   16   15   18  (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14)  17   16   15   18  (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14)  17   16   15   18  (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14)  17   16   15  (18) (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14)  15   16   17  (18) (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14) (15)  16   17  (18) (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14) (15)  16   17  (18) (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14) (15)  16  (17) (18) (19) (20) (21) (22)
     |
     |  (10) (11) (12) (13) (14) (15)  16  (17) (18) (19) (20) (21) (22)
     |
 MEDIAN: A[6] = 16

Median where the algorithm terminates fairly early
     |                                  ^
   0 |    0    1    2    3    4    5    6    7    8    9   10   11   12 
-----|------------------------------------------------------------------
     |   43   22   51   19   11   67   13   36   49   28   15   32   38 
     | 
     |   22   19   11   13   36   28   15   32   38   67   43   51   49 
     | 
     |   22   19   11   13   36   28   15   32  (38) (67) (43) (51) (49)
     | 
     |   22   19   11   13   28   15   32   36  (38) (67) (43) (51) (49)
     |
 MEDIAN: A[6] = 32

Revision date: 2012-02-10. (Please use ISO 8601, the International Standard.)