Algorithms for Merging and Sorting Data Files

Merging two sorted files

Merge(VectorA, VectorB, VectorC)

I=J=K=1

WHILE I ≤ M AND J ≤ N DO

IF VectorA(I) < VectorB(J) THEN

VectorC(K) = A(I)

I=I+1

K=K+1

ELSE

IF VectorA(I) > B(J) THEN

VectorC(K) = VectorB(J)

J=J+1

K=K+1

ELSE

VectorC(K) = VectorA(I)

I=I+1

J=J+1

K=K+1

ENDIF

ENDIF

ENDWHILE

IF I > M THEN

FOR R = J TO N STEP 1 DO

VectorC(K) = VectorB(R)

K= K + 1

NEXT R

ELSE

FOR R = I TO M STEP 1 DO

VectorC(K) = VectorA(R)

K=K+1

NEXT R

ENDIF

END

Algorithm for Insertion Sort

{Look at each card in turn, starting with the second card}

FOR Position = 2 to n DO

CurrentValue = Vector[Position]

{Keep value of current number}

{and store it in position 0}

Vector[0] = CurrentValue

{Now look at each number to the left of current number (Position – 1) and move

each number right if it is greater than CurrentValue. If the number is not greater

than CurrentValue, insert CurrentValue.}

Pointer = Position - 1

WHILE Vector[Pointer] > CurrentValue DO

Vector[Pointer + 1] = Vector[Pointer]

{Move left one place}

Pointer = Pointer – 1

ENDWHILE

Vector[Pointer + 1] = CurrentValue

ENDFOR

END

Algorithm for Quick Sort

QuickSort(Vector, LB, UB)

IF LB <> UB THEN

{There is more than one element in Vector, therefore it needs sorting}

Set I = LB

Set J = UB

REPEAT

WHILE I <> J AND Vector[I] < Vector[J] DO

{Move right pointer left}

Make J = J – 1

ENDWHILE

IF I<> J THEN swap Vector[I] and Vector[J]

WHILE I <> J AND Vector[I] < Vector[J] DO

{Move left pointer right}

Make I = I + 1

ENDWHILE

IF I <> J THEN swap Vector[I] and Vector[J]

UNTIL I = J

{Value now in correct position}

{So sort left sublist}

QuickSort(Vector, LB, I – 1)

{Now sort right sublist}

QuickSort(Vector, I + 1, UB)

ENDIF

END