Wave Sort (W-Sort) Research Paper

This repository contains the LaTeX source files, figures, and compilation scripts for the research paper:

Wave Sort (W-Sort): A Novel In-Place Algorithm with Dynamic Pivoting for Consistent Performance and Logarithmic Stack Depth

• arXiv Paper: arXiv:2505.13552
• Author: Jia Xu Wei (University of California, Davis)

---

Abstract

Modern comparison sorts like quicksort suffer from performance inconsistencies due to suboptimal pivot selection, leading to $O(N^2)$ worst-case complexity, while in-place merge sort variants face challenges with data movement overhead. We introduce Wave Sort, a novel in-place sorting algorithm that addresses these limitations through a dynamic pivot selection strategy. Wave Sort iteratively expands a sorted region and selects pivots from this growing sorted portion to partition adjacent unsorted data.

---

Compilation

You can compile this LaTeX document locally.

Prerequisite

Install TeX Live dependencies (Ubuntu/Debian/Mint):

sudo apt update
sudo apt install -y texlive-latex-recommended texlive-latex-extra texlive-fonts-recommended texlive-bibtex-extra latexmk

Build Commands

A Makefile is provided to make compilation easy:

• Build PDF: make (generates PDF at output/main.pdf)
• Clean Auxiliary Files (keeps output/main.pdf): make clean

---

Repository Structure

• main.tex — Main LaTeX document entry point.
• wlpeerj.cls — Unofficial LaTeX PeerJ journal class.
• sample.bib — Reference bibliography file.
• sections/ — Subdirectories containing individual paper sections.
• Fig*.pdf and Fig*.png — Figure illustrations used in the paper.