merge_sorted.F90

Go to the documentation of this file.

!! Copyright (C) 2021 S. Ohlmann
!!
!! This Source Code Form is subject to the terms of the Mozilla Public
!! License, v. 2.0. If a copy of the MPL was not distributed with this
!! file, You can obtain one at https://mozilla.org/MPL/2.0/.
!!
#include "global.h"
 
module merge_sorted_oct_m
  use debug_oct_m
  use global_oct_m
  use heap_oct_m
  implicit none
 
  private
  public :: merge_sorted_arrays
 
contains
  ! Merge a number of sorted arrays
  ! The sorted arrays are linearly ordered in array and their sizes are given in sizes.
  ! The merged array is returned and optionally also an index map that can be used
  ! to also merge another data array.
  !
  ! This routine uses a minheap to to a k-way merge.
  subroutine merge_sorted_arrays(array, sizes, merged, index_map)
    integer(int64),       intent(in)    :: array(:)
    integer,           intent(in)    :: sizes(:)
    integer(int64),       intent(inout) :: merged(:)
    integer, optional, intent(inout) :: index_map(:)
 
    type(heap_t) :: heap
 
    push_sub(merge_sorted_arrays)
 
    call heap%init(array, sizes)
    call heap%merge(merged, index_map)
    call heap%end()
 
    pop_sub(merge_sorted_arrays)
  end subroutine merge_sorted_arrays
end module merge_sorted_oct_m