@Override
        public void sort(int[] array) {
                if (array.length > 1) {
                        // split array into two  halves
                        int[] left = leftHalf(array);
                        int[] right = rightHalf(array);

                        // recursively sort the two halves
                        sort(left);
                        sort(right);

                        // merge the sorted halves into a sorted whole
                        merge(array, left, right);
                }
        }