Abstract
Given two sorted arrays A = (a1,a2, ⋯ ,an) and B = (b1,b2, ⋯ ,bn) of records such that (1) the n records are sorted according to one field which is called the key, and (2) the values of the keys are serial numbers. Merging data records has many applications in computer science especially in database. We develop an algorithm that runs in O(logn) time on EREW PRAM to merge two sorted arrays of records using \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\frac{n}{\log{n}}$\end{document} processors even the keys of the data records are repeated. The algorithm is cost-optimal, deterministic, stable and uses linear number of space.