Input array: 64 90 68 67 15 51 81 50 13 10 77 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 4 32 63 60 99 23 98 Splitter maintains an array section of smaller numbers to the left, in blue, and a section of large numbers to the right, in green. Unprocessed numbers in the middle are in red. Enter split: bottom = 0, top= 48, split value= 64 64 90 68 67 15 51 81 50 13 10 77 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 4 32 63 60 99 23 98 64 23 68 67 15 51 81 50 13 10 77 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 4 32 63 60 99 90 98 64 23 60 67 15 51 81 50 13 10 77 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 4 32 63 68 99 90 98 64 23 60 63 15 51 81 50 13 10 77 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 4 32 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 77 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 4 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 82 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 30 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 66 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 42 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 82 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 49 66 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 72 68 75 37 29 36 78 90 89 86 9 27 30 81 4 98 82 66 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 68 75 37 29 36 78 90 89 86 9 27 30 81 72 98 82 66 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 75 37 29 36 78 90 89 86 9 27 68 81 72 98 82 66 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 27 37 29 36 78 90 89 86 9 75 68 81 72 98 82 66 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 27 37 29 36 9 90 89 86 78 75 68 81 72 98 82 66 82 81 73 77 81 67 68 99 90 98 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 27 37 29 36 9 90 89 86 78 75 68 81 72 98 82 66 82 81 73 77 81 67 68 99 90 98 Exit split: split at= 27 Enter split: bottom = 0, top= 27, split value= 64 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 27 37 29 36 9 64 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 27 37 29 36 9 Exit split: split at= 27 Enter split: bottom = 0, top= 26, split value= 9 9 23 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 4 30 27 37 29 36 9 4 60 63 15 51 32 50 13 10 4 29 16 16 60 2 30 42 49 43 23 30 27 37 29 36 9 4 2 63 15 51 32 50 13 10 4 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 9 4 2 4 15 51 32 50 13 10 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 9 4 2 4 15 51 32 50 13 10 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 Exit split: split at= 4 Enter split: bottom = 0, top= 4, split value= 9 9 4 2 4 9 4 2 4 Exit split: split at= 4 Enter split: bottom = 0, top= 3, split value= 4 4 4 2 4 4 2 Exit split: split at= 3 Enter split: bottom = 0, top= 2, split value= 2 2 4 2 4 Exit split: split at= 1 Enter split: bottom = 4, top= 26, split value= 15 15 51 32 50 13 10 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 15 10 32 50 13 51 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 15 10 13 50 32 51 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 15 10 13 50 32 51 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 Exit split: split at= 7 Enter split: bottom = 4, top= 7, split value= 15 15 10 13 15 10 13 Exit split: split at= 7 Enter split: bottom = 4, top= 6, split value= 13 13 10 13 10 Exit split: split at= 6 Enter split: bottom = 7, top= 26, split value= 50 50 32 51 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 36 50 32 36 63 29 16 16 60 60 30 42 49 43 23 30 27 37 29 51 50 32 36 29 29 16 16 60 60 30 42 49 43 23 30 27 37 63 51 50 32 36 29 29 16 16 37 60 30 42 49 43 23 30 27 60 63 51 50 32 36 29 29 16 16 37 27 30 42 49 43 23 30 60 60 63 51 50 32 36 29 29 16 16 37 27 30 42 49 43 23 30 60 60 63 51 Exit split: split at= 22 Enter split: bottom = 7, top= 22, split value= 50 50 32 36 29 29 16 16 37 27 30 42 49 43 23 30 50 32 36 29 29 16 16 37 27 30 42 49 43 23 30 Exit split: split at= 22 Enter split: bottom = 7, top= 21, split value= 30 30 32 36 29 29 16 16 37 27 30 42 49 43 23 30 23 36 29 29 16 16 37 27 30 42 49 43 32 30 23 30 29 29 16 16 37 27 36 42 49 43 32 30 23 30 29 29 16 16 27 37 36 42 49 43 32 30 23 30 29 29 16 16 27 37 36 42 49 43 32 Exit split: split at= 15 Enter split: bottom = 7, top= 15, split value= 30 30 23 30 29 29 16 16 27 30 23 30 29 29 16 16 27 Exit split: split at= 15 Enter split: bottom = 7, top= 14, split value= 27 27 23 30 29 29 16 16 27 23 16 29 29 16 30 27 23 16 16 29 29 30 27 23 16 16 29 29 30 Exit split: split at= 11 Enter split: bottom = 7, top= 11, split value= 27 27 23 16 16 27 23 16 16 Exit split: split at= 11 Enter split: bottom = 7, top= 10, split value= 16 16 23 16 16 16 23 16 16 23 Exit split: split at= 9 Enter split: bottom = 7, top= 9, split value= 16 16 16 16 16 Exit split: split at= 9 Enter split: bottom = 11, top= 14, split value= 29 29 29 30 29 29 30 Exit split: split at= 13 Enter split: bottom = 11, top= 13, split value= 29 29 29 29 29 Exit split: split at= 13 Enter split: bottom = 15, top= 21, split value= 37 37 36 42 49 43 32 37 36 32 49 43 42 37 36 32 49 43 42 Exit split: split at= 18 Enter split: bottom = 15, top= 18, split value= 37 37 36 32 37 36 32 Exit split: split at= 18 Enter split: bottom = 15, top= 17, split value= 32 32 36 32 36 Exit split: split at= 16 Enter split: bottom = 18, top= 21, split value= 49 49 43 42 49 43 42 Exit split: split at= 21 Enter split: bottom = 18, top= 20, split value= 42 42 43 42 43 Exit split: split at= 19 Enter split: bottom = 22, top= 26, split value= 60 60 60 63 51 60 60 51 63 60 60 51 63 Exit split: split at= 25 Enter split: bottom = 22, top= 25, split value= 60 60 60 51 60 60 51 Exit split: split at= 25 Enter split: bottom = 22, top= 24, split value= 51 51 60 51 60 Exit split: split at= 23 Enter split: bottom = 27, top= 48, split value= 90 90 89 86 78 75 68 81 72 98 82 66 82 81 73 77 81 67 68 99 90 98 90 89 86 78 75 68 81 72 90 82 66 82 81 73 77 81 67 68 99 98 98 90 89 86 78 75 68 81 72 90 82 66 82 81 73 77 81 67 68 99 98 98 Exit split: split at= 45 Enter split: bottom = 27, top= 45, split value= 90 90 89 86 78 75 68 81 72 90 82 66 82 81 73 77 81 67 68 90 89 86 78 75 68 81 72 90 82 66 82 81 73 77 81 67 68 Exit split: split at= 45 Enter split: bottom = 27, top= 44, split value= 68 68 89 86 78 75 68 81 72 90 82 66 82 81 73 77 81 67 68 67 86 78 75 68 81 72 90 82 66 82 81 73 77 81 89 68 67 66 78 75 68 81 72 90 82 86 82 81 73 77 81 89 68 67 66 68 75 78 81 72 90 82 86 82 81 73 77 81 89 68 67 66 68 75 78 81 72 90 82 86 82 81 73 77 81 89 Exit split: split at= 31 Enter split: bottom = 27, top= 31, split value= 68 68 67 66 68 68 67 66 68 Exit split: split at= 31 Enter split: bottom = 27, top= 30, split value= 68 68 67 66 68 67 66 Exit split: split at= 30 Enter split: bottom = 27, top= 29, split value= 66 66 67 66 67 Exit split: split at= 28 Enter split: bottom = 31, top= 44, split value= 75 75 78 81 72 90 82 86 82 81 73 77 81 89 75 73 81 72 90 82 86 82 81 78 77 81 89 75 73 72 81 90 82 86 82 81 78 77 81 89 75 73 72 81 90 82 86 82 81 78 77 81 89 Exit split: split at= 34 Enter split: bottom = 31, top= 34, split value= 75 75 73 72 75 73 72 Exit split: split at= 34 Enter split: bottom = 31, top= 33, split value= 72 72 73 72 73 Exit split: split at= 32 Enter split: bottom = 34, top= 44, split value= 81 81 90 82 86 82 81 78 77 81 89 81 81 82 86 82 81 78 77 90 89 81 81 77 86 82 81 78 82 90 89 81 81 77 78 82 81 86 82 90 89 81 81 77 78 81 82 86 82 90 89 81 81 77 78 81 82 86 82 90 89 Exit split: split at= 39 Enter split: bottom = 34, top= 39, split value= 81 81 81 77 78 81 81 81 77 78 81 Exit split: split at= 39 Enter split: bottom = 34, top= 38, split value= 81 81 81 77 78 81 81 77 78 Exit split: split at= 38 Enter split: bottom = 34, top= 37, split value= 78 78 81 77 78 77 81 78 77 81 Exit split: split at= 36 Enter split: bottom = 34, top= 36, split value= 78 78 77 78 77 Exit split: split at= 36 Enter split: bottom = 39, top= 44, split value= 82 82 86 82 90 89 82 82 86 90 89 82 82 86 90 89 Exit split: split at= 41 Enter split: bottom = 39, top= 41, split value= 82 82 82 82 82 Exit split: split at= 41 Enter split: bottom = 41, top= 44, split value= 86 86 90 89 86 90 89 Exit split: split at= 42 Enter split: bottom = 42, top= 44, split value= 90 90 89 90 89 Exit split: split at= 44 Enter split: bottom = 45, top= 48, split value= 99 99 98 98 99 98 98 Exit split: split at= 48 Enter split: bottom = 45, top= 47, split value= 98 98 98 98 98 Exit split: split at= 47 Output array: 2 4 4 9 10 13 15 16 16 23 27 29 29 30 30 32 36 37 42 43 49 50 51 60 60 63 64 66 67 68 68 72 73 75 77 78 81 81 81 82 82 86 89 90 90 98 98 99