Some simple in-place merging algorithms |
| |
Authors: | Jin Kue Wong |
| |
Institution: | (1) Computer Science Department, University of Ottawa, K1N 9B4 Ottawa, Ontario, Canada;(2) Present address: Bell-Northern Research, Station C, P.O. Box 3511, K1Y 4H7 Ottawa, Ontario, Canada |
| |
Abstract: | The theoretical presentation and analysis is given for two families of simple in-place merging algorithms and their limiting cases. The first family merges stably inO(k·n) time andO(n
1/k
) additional space with a limiting case running inO(n logn) time and constant space. The second family merges unstably inO (k ·n) time andO(log
k
n) space with a limiting case running inO(nG(n)) time and constant space. HereG(n) is the leastk such thatF(k) n whereF(0)=1 andF(i)=2
F(i–1) fori1. Each algorithm gives rise to a corresponding merge sort. |
| |
Keywords: | merging sorting in-place analysis of algorithms |
本文献已被 SpringerLink 等数据库收录! |
|