Skip to main content

Alogrithm to sort a huge list of numbers in O(n) complexity in Java

A large file of numbers can be sorted in O(n) complexity by using a large bit array of the size same as the largest number in the list of numbers to be sorted. It can be done in Java using BitSet.


package com.biplav.algorithms;

import java.util.Arrays;

import com.biplav.ds.BitArray;


public class SortMillionNumbersWithGivenMax { //n+m


public static int[] sort(int[] list, int max) {
int[] sortedList = new int[list.length];
//BitSet bitSet = new BitSet(max);
BitArray bitSet = new BitArray(max);
for(int n:list) bitSet.set(n); //n
int index=0;
for(int i =0 ; i<=  max; i++) { //m
if(bitSet.get(i)) {
sortedList[index++] = i;
}
}
return sortedList;
}

public static void main(String[] args) {
int[] list = new int[]{1,2,3,4,5,9,15,18,25,7,11};
System.out.println(Arrays.toString(sort(list, 27)));
}
}

I have used BitArray defined by me. Its implementation is:

package com.biplav.ds;

public class BitArray {
 private byte[] arrayOfSize8bit;

 public BitArray(int size) {
  arrayOfSize8bit = new byte[(size / 8) + (size % 8 == 0 ? 0 : 1)];
 }

 public boolean get(int location) {
  return (arrayOfSize8bit[location / 8] & 1 << location % 8) != 0;
 }

 public void set(int location, boolean value) {
  byte b8 = arrayOfSize8bit[location / 8];
  byte posBit = (byte) (1 << (location % 8));
  if (value) {
   b8 = (byte) (b8 | posBit);
  } else {
   b8 = (byte) (b8 & (255 - posBit));
  }
  arrayOfSize8bit[location / 8] = b8;
 }

 public void set(int location) {
  set(location, true);
 }

 public void unset(int location) {
  set(location, false);
 }
}

Instead of BitArray BitSet can also be used which uses long[] instead of Byte array to achieve something similar.

Popular posts from this blog

Why India Hasn’t Built Its GPT Moment (Yet)

India has the world’s third-largest startup ecosystem, a thriving developer base, and a mobile-first population larger than the US and Europe combined. Yet, no GPT-4. No DeepMind. No Amazon-style platform. Why? Innovation Isn’t Accidental—It’s Engineered The Zerodha Daily Brief recently asked why India hasn’t built a global product company like Apple. The key argument: India isn’t building for the world. It’s solving for local constraints, scale, and affordability—but global scale requires deep IP, design, and tech differentiation. It’s not just about software, it’s about systems thinking. More importantly, it answers the question: Why do countries innovate? The answer isn’t just genius or ambition—it’s incentives and ecosystems. The U.S. Defense Department, for example, accounted for nearly 70% of federal R&D funding during the Cold War. China has pumped billions into semiconductors and AI with long-term national alignment. These aren’t short-term bets—they are strategic, delibe...

From Stubborn to Smart: How I Learned to Use AI as a PM

Listen to the article in podcast format on PM-AI Diaries channel on Spotify! Ever since I published "The Death of the Stubborn PM" back in February, my inbox has been buzzing with one big question: “Okay, I get that AI is the future for product managers—but how do I actually use it?” It’s a fair ask. In that piece, I argued that PMs who resist AI are doomed to fade away, like dinosaurs refusing to evolve. As I wrote, “The stubborn PM who clings to old ways will die out, replaced by those who harness AI’s power while leaning into what makes us human.” Now, people want the playbook. So, let’s walk through it with a story—my own journey of figuring this out, backed by some sharp insights from MIT Sloan’s "When Humans and AI Work Best Together—and When Each Is Better Alone" . The Wake-Up Call Picture me a few months back: a PM buried in work, juggling a dozen tasks, and feeling like there weren’t enough hours in the day. Writing user stories, sketching ideas, track...

The Death of the Stubborn PM

Product Management is undergoing a seismic shift, much like programming did when compilers replaced assembly language or when Agile dismantled waterfall dogma. Stubborn PMs who cling to outdated rituals—like treating PRDs as sacred texts—will fade into irrelevance. The future belongs to those who embrace AI as a collaborator, not a threat.   AI Will Disrupt the Tactics, Not the Thinking   Historically, tools abstracted manual work: compilers automated code translation, A/B testing replaced gut-driven debates. Similarly, AI will automate tactical PM tasks—data aggregation, routine prioritization, even drafting specs. But this is liberating, not limiting.   The stubborn PM obsesses over *how* to write a PRD; the adaptive PM focuses on *why* a product should exist. AI can’t replicate judgment calls that demand intuition: interpreting unmet customer needs, balancing ethics with growth, or navigating ambiguity when data is sparse. As AI handles execution, the PM...