dbcsr_1d_i4_sort Subroutine

      subroutine dbcsr_1d_i4_sort(arr, n, indices)
      !! Sorts an array inplace using a combination of merge- and bubble-sort.
      !! It also returns the indices, which the elements had before the sort.

         integer, intent(in)                  :: n
         !! length of array
         INTEGER(kind=int_4), dimension(1:n), intent(inout) :: arr
         !! the array to sort
         integer, dimension(1:n), intent(out)   :: indices
         !! returns elements-indices before the sort

         integer :: i
         INTEGER(kind=int_4), pointer, CONTIGUOUS     :: tmp_arr(:)
         integer, pointer, CONTIGUOUS       :: tmp_idx(:)

         if (n == 0) return ! for some reason this is a frequent case in cp2k

         ! scratch space used during the merge step
         allocate (tmp_arr((size(arr) + 1)/2), tmp_idx((size(arr) + 1)/2))

         indices = (/(i, i=1, size(arr))/)

         call dbcsr_1d_i4_sort_low(arr(1:n), indices, tmp_arr, tmp_idx)

         deallocate (tmp_arr, tmp_idx)

      end subroutine dbcsr_1d_i4_sort