Merge Sort TypeScript Project

This project implements a merge function that combines three sorted arrays into a single sorted array. The function handles the following conditions:

• collection_1 and collection_3 are sorted in ascending order
• collection_2 is sorted in descending order

Prerequisites

• Node.js (v14 or higher)
• npm (Node Package Manager)

Setup

1. Clone the repository:

git clone https://github.com/yourusername/merge-sort.git
cd merge-sort

2. Install dependencies:

npm install

Project Structure

merge-sort/
├── src/
│   ├── index.ts        # Main entry point with example usage
│   ├── merge.ts        # Merge function implementation
│   └── merge.test.ts   # Unit tests
├── dist/               # Compiled JavaScript files
├── package.json        # Project configuration and dependencies
├── tsconfig.json       # TypeScript configuration
├── jest.config.js      # Jest test configuration
└── README.md           # Project documentation

Usage

Running Tests

To run the unit tests:

npm test

Building the Project

To compile the TypeScript code:

npm run build

Running the Example

To run the example code:

npm start

This will execute the example in src/index.ts which demonstrates the merge function with sample arrays.

Function Interface

merge(collection1: number[], collection2: number[], collection3: number[]): number[]

Parameters:

• collection1: Array of numbers sorted in ascending order
• collection2: Array of numbers sorted in descending order
• collection3: Array of numbers sorted in ascending order

Returns:

• A new array containing all elements from the input arrays, sorted in ascending order

Example

import { merge } from './merge';

const collection1 = [1, 3, 5];  // ascending
const collection2 = [6, 4, 2];  // descending
const collection3 = [0, 7, 8];  // ascending

const result = merge(collection1, collection2, collection3);
console.log(result); // Output: [0, 1, 2, 3, 4, 5, 6, 7, 8]

Test Cases

The implementation is thoroughly tested with the following test cases:

Test Case 1: Basic Merge Operation

test('should merge three sorted arrays correctly', () => {
    const collection1 = [1, 3, 5];  // ascending
    const collection2 = [6, 4, 2];  // descending
    const collection3 = [0, 7, 8];  // ascending
    
    const result = merge(collection1, collection2, collection3);
    
    expect(result).toEqual([0, 1, 2, 3, 4, 5, 6, 7, 8]);
});

Test Case 2: Empty Arrays

test('should handle empty arrays', () => {
    const collection1: number[] = [];
    const collection2: number[] = [3, 2, 1];
    const collection3: number[] = [];
    
    const result = merge(collection1, collection2, collection3);
    
    expect(result).toEqual([1, 2, 3]);
});

Test Case 3: Different Array Lengths

test('should handle arrays of different lengths', () => {
    const collection1 = [1, 5];     // ascending
    const collection2 = [6, 4, 2];  // descending
    const collection3 = [3];        // ascending
    
    const result = merge(collection1, collection2, collection3);
    
    expect(result).toEqual([1, 2, 3, 4, 5, 6]);
});

Test Case 4: Duplicate Values

test('should handle arrays with duplicate values', () => {
    const collection1 = [1, 2, 2];  // ascending
    const collection2 = [3, 2, 1];  // descending
    const collection3 = [2, 3, 3];  // ascending
    
    const result = merge(collection1, collection2, collection3);
    
    expect(result).toEqual([1, 1, 2, 2, 2, 2, 3, 3, 3]);
});

Features

• Type-safe implementation using TypeScript
• Comprehensive unit tests
• No use of built-in sort functions
• Handles edge cases:
  • Empty arrays
  • Arrays of different lengths
  • Arrays with duplicate values